I've thought about this idea a few times... and there's only one solution I can come up with:
A Content Generator.
It would have to be robust, much more robust than, say, the instance generator in a MMO like City of Heroes (the only one I've played)... A Planet content Generator would have to have modules (and sub modules) for Terrain/Atmosphere, NPCs, Social Structure, Government, Architecture, Resources, Conflict and Anomalies... the Anomaly generator would have to have similar modules, including one for PC and NPC effects.
It would have to be able to generate millions of diverse worlds, not all wholly different, but different enough that a player could travel to 100 or so and not note any glaring similarities.
NPC text would have to be written in a way that adapts it to a variety of situations... perhaps even make certain text modular to account for low-tech and high-tech societies. A set of 100-200 NPC classes (coding-term) would be created, and have text and 10-20 quests attached to them, but each implementation of that NPC (ie Tvon of Yalu IV) would only provide one or two, depending on the supposed 'size' of the planet.
Of course, there would be static worlds, the ones that we've seen multiple times in the shows. But those swaths of space? They'd have to be chocked full of different places to explore. Some of which will not appear on a simple long-range sensor-scan. The rewards? In addition to some level of discovery credit, players get access to all those great missions planetside (or shipside in the case of anomalies) and their rewards.
To slide advancement into this pseudo-random instancing is easy: Have certain modules only available as players progress to certain ranks or skill requirements, or only be associated with missions given at certain points in advancement by Starfleet. To make newbs feel small, give certain sections of space a minimum difficulty setting before they begin to adapt to the players, so that Newbies that take their first runabout straight for deep space will get creamed. Some sections of space will simply be extremely perilous, even for crews of intermediate toons.
Offering tons of different module types to explore gives explorers ever the chance of seeing 'something new' when they see a new anomaly or visit a new planet. If the surprises are relatively frequent, with randomized instancing as 'levelling filler' then explorers can feel motivated to continue to push into the random areas.