I'd like to show Cryptic the playerbase's creative side and offer constructive ideas for exploration missions meant to be usable by both Federation and Klingon players. They are intended to be somewhat generic and repeatable. Not that they couldn't be used in real missions, of course.
1. Tag or kill X number of neutral mobs on a planet. A neutral mob is one that is attackable, but will not attack you first. This involves going up to the mob and using a temporary power on it. The mobs move quickly so they need to be chased down. Alternatively, you can kill it instead if that fits your play style. Tagging it with the temp power is easier and quicker, but killing it nets you loot. An example is studying wild alien animals. Up to you if you do that by hitting them with tracking darts or bringing them up to your ship as corpses to be dissected.
2. Multiple choice quiz missions in the style of the early miner's strike mission. As this requires a lot of writing, consider having a contest to allow players to submit all required text for it. Text approved for it net the player a very minor award (title, coloured tribble, etc). This admittedly would require a lot of work.
3. Study Anomaly. Ship encounter a Big Swirly Thing in space (as a set of mobs, a la the Briar Patch) that is invincible to normal weapons, but 'attacks' with some sort of damage aura. Players must go to a point near or inside it to investigate, surviving using their shields, a temp power based on technobabble (Tachyon Burst! Deflector Dish Polarization! Shield Modulation!) that debuffs the damage aura, and a temp power that shields the player, etc. Full Impulse is disabled.
4. Settle Dispute. Two NPC ships/fleets are fighting (but won't conclude until you make a decision). Both can be hailed and they'll give their side of the story. Players can a) Take one side and blow up the opposite ship. This nets them loot from that ship. b) Take one side but only disable the opposite ship. This nets them a reward from the ship they sided with, but lesser than whatever loot they would have gotten from killing it, as disabling is easier. c) Kill/disable both ships. They'll team up against you. Nets you loot from both ships. d) Not get involved. This nets no reward, but does complete the 1/3rd explore system requirement for the overall exploration mission. This also works as a ground mission.
5. Blockade Run. A ship must get from the Spawn Point A to Destination Point B (no Full Impulse). They are getting attacked by multiple ships throughout. Although the attacking ships can be destroyed, they will always be replaced by a new enemy within about 30 seconds and so is only a short respite. Thus it's a defensive battle, though maintaining some offence will buy you extra time. Story explanations can range from running a blockade to deliver supplies/medicine/weapons/etc to accidentally warping to a perviously unknown enemy stronghold and having to escape.
6. Ship in Distress. An NPC ship is badly damaged by the enemy faction. Players must keep the ship alive for X minutes by using a temporary power that heals the NPC ship, while also fighting the enemy.
7. Dreadnaught Destruction. Players encounter an enemy ship/missile en route to attack their faction and/or a neutral innocent planet, much like that one super Cardassian missile from Voyager. They may either destroy the enemy ship/missile/whatever with their ship, or beam aboard and disable it, fighting mobs. This is simply an excuse for a short battle. It is up to the player to decide if they prefer it to be ground or space.
8. Obstacle Course. Players must navigate an obstacle course of stationary mobs (asteroids, mines, small Swirly Things) to get to point B. Hitting/getting too close to the mob damages the ship. Up to them on how quick they're willing to go.
9. Ancient Relic. Players find an ancient floating space relic/ship/museum. May either beam aboard to get glowies & read lore ridbits about this ancient civilization (nets a small reward), run a quick scan and then ignore it (nets no reward but completes 1/3rd of the overall exploration mission requirement), or blow it up to nobody else can get it (very minor loot reward).