1) Start it with the duty roster. A "mission to explore this sector". Your officer returns, and says "that was interesting" (or not!), opening up a captain mission.
[this rate-limits the number of missions, ties the system into the c-store in some manner, and also allows for blue/purple missions]
2) The mission itself should have a decent reward, regardless of how trivial it is - they are rate limited by the duty roster, so no major problems here.
3) A mission should exist in several near-identical forms that can't be guessed by the player on arrival, if the mission doesn't need a space/ground component then it doesn't have one.
a) It all goes well, you stick a flag on the planet and return home to parades!!
b) Local wildlife is not so friendly.
c) It's a trap!
d) there's an artifact on the planet, collecting enough of these bits opens a new (rare) mission.
e) You meet someone, have a chat, and they give you a duty officer and it opens up duty missions with them.
f) A puzzle or whatever.
g) "diplomacy" although I have no idea how you could do that really.
The key is that the player shouldn't know the 'twist' until at least half-way through the mission, keeping things interesting... some of the outcomes should be 'incredibly' dangerous, some incredibly valuable.
Ok, this may seem like one other game out there, but... I think exploration is more about searching than it is about finding. So, here's what kind of exploration I would expect from a Star trek game:
1. You wander off to a star cluster. The cluster itself is not a monotonous cube of space. It has various anomalies (I mean visible ones, like nebulae, stellar nurseries, etc ). It has landmarks, and thus is intersting to navigate.
2. You begin with a long-range scan. Something Seven of Nine did in her astrometrics. Scan returns you some choices of star systems nearby. Probably, other stellar phenomenon, like an unstable wormhole, cosmic string or whatever.
3. You choose the system or phenomenon that you would like to investigate. Let's say it's a star system. It appears on the map and you navigate to it.
4. At close proximity of the system you make another scan and see a choice of points of interest. Lets say, the system has three planets and an asteroid belt. One of the planets has a derelict ship in orbit. There are traces of an unusual particles in the atmosphere of another planet. Finally, it seems like asteroid belt has some dilithium.
5. You don't feel like exploring any ship hulks or searching for more particle traces. So, you assign some DOffs to mine that dilithium, and warp to the remaining M-Class planet. Once in orbit, your sensors pick some points of interest on the surface: a peculiar life form at one site, some ancient ruins on the other, and a faint artificial energy signature emanating from a network of caves.
6. You beam down to the ancient ruins with an away team, fend off some wildlife/hostile aliens/ancient security systems. Then you find an unknown artifact, and return to your ship. You put the artifact in the trusty hands of your DOffs and call it a day.
7. Or, you warp to that derelict ship you detected earlier.
...And I know the problem here: this game mechanics requires a lot of game design work. Even if the sector/system/planet scan part is just a new UI (like DOff). Leaving UI aside, there have to be a lot of maps for various exploration sites and encounters, so that the whole thing does not seem repetitive (although, even with finite number of maps, you can randomize such things as backdrops/skyboxes, lighting, props, and NPCs).