@Aldarc, that's a provocative OP. It prompts a number of thoughts in me. I'll post some of them!
What makes for a good setting premise as it relates to the PCs? I want a setting to provide genre and tropes. In D&D or comparable FRPGing, that means I need forests (for elves and goblins), mountains (for dwarves and orcs), a city or two (for thieves and barons and merchants), maybe an uncharted desert or a hidden plateau, etc.
I ran a 30-level 4e D&D campaign using the inside gatefold-cover map from the B/X module Night's Dark Terror. I haven't done a precise comparison but it's probably similar in size to the Nentir Vale. And it ticks all the boxes. From mid-paragon a lot of the action took place "off the map" - in the Underdark (where I maintained a simple 1 page sketch map) or on other planes.
My Burning Wheel campaigns (both the one I GM and the one I play in) use the Greyhawk maps. The middle of those maps has Celene for elves, the Lortmils for dwarves, the Pomarj for Orcs, Greyhaw, Dyvers and Hardby as cities, the Bright Desert, pirates along the Wild Coast, etc. It's excellent for tropes.
I don't generally need details of the sort some other posters have mentioned. That can be worked out as required, in play. But some names and places to kick things off are helpful. (In our Prince Valiant game the map of Britain on the inside cover of Pendragon, plus maps of Europe, North Africa and West Asia c 800 CE taken from a historical atlas serve much the same purpose.)
In my Classic Traveller game most of the worlds are randomly generated (using the relevant mechanical procedure) but they are not fully random in their relationship to one another - some of that has been worked out during play to support the direction of play - and some of their key features have been worked out directly in response to player interest for their PCs: it's because one PC is all about finding alien civilisations, and another is all about learning psionic powers, that currently the PCs are excavating a 2 billion year old alien-constructed psionically-oriented pyramid complex embedded in 4 km of ice. (The fact that there are also psionically inclined xeno-morph-y aliens, on the other hand, is a GM-introduced thing inspired by reading about the new Alien RPG on these boards a year or so ago.)