Rather than running from one console to the next to do three boring scans, there could open up a window with some kind of circuit diagram. You need to reorganize some parts of the diagram in order to bring back energy online or something else. This could vary in way, that sometimes u only can use what u got on the diagram and sometimes u got spare parts u may pick from or there may be a time limit, after which the diagram resets and u need to try over... (not more, starting a whole mission over will be frustrating).
And that's just one of almost infinite possibilities.
And some other kinds of mission could be an attacking life form on a planet and u have to defend a outpost / village / whatever against waves of attackers.
An idea that would make some great PvP maps: One fraction needs to defend something and the other fraction storms. Whenever the attackers take over a location, the enemies spawnpoints will set back to the next point.
This kind of map could be used to bring more enemies of one fraction onto a map: 5 klingons defending, 15 feds attacking... of course the klingons got some defensive weapons on their side and got a much shorter way to the locations they need to defend.
Hell... I could write on and on... maybe u see the potential in this.
Here is another idea: you have just finished an exploration mission and reported to Starfleet to get your reward. You receive it, then your ship rocks and you drop out of hyperspace (warp, whatever. That area we are flying through when not in a system). Now, you and your bridge crew have to travel around your own ship to fix it before you can go on any other missions. The is no loot drop for a mission like this, but you gain experience points as do your BOs.
These should be random. You never know when one will occur or what will cause it.
Personally, I liked the very opening of the game (when you are an ensign) and you have to beam to another ship and help restore its systems. How come the only room on our own ship we can visit is the bridge?
To take it a bit farther, there should be more variety of scanning systems and the ability to scan for specific things such as identifying life forms, natural energy sources/types, inert material makeup etc. For engineering run scans to determine fuction of unknown technology, artificial engergy sources, composite material makeup etc. The ability to replicate needed items/tools would be nice as well.