[Loslote]

I would say there would be more opportunity for fame in the First Age, not because of class differences, but because the various realms were less fragmented. Heroes of Rohan would not be known in the other realms - but, beside the obvious exception (Gondolin) the realms of the First Age kept fairly well abreast of the news from the other realms.

This actually makes the argument for Mordor more persuasive, though, since Mordor's fame unifies all of those fragmented realms in fear. I'd probably be inclined at this point to say my top two are Tol-in-Gaurhoth and Mordor - surprise twist!