Obviously, they need to fix some of the broken missions first, before adding new ones.
With the Holodeck concept, there are quite literally unlimited potential for players to revisit old missions and to set up their own missions etc. However, I had a few ideas I wanted to share anyway;
1- First Contact: Players must done a special "chain armor" to look like the locals, then weilding only melee weapons (swords) their bridge crew must undertake the mission, which is perhaps if you are using a random generator they must recover a rogue starfleet officer or left behind technology without being discovered by the locals (involves some stealth or clever distractions, or just fighting your way through it)
2-Rip almost any episode out of TNG or Star Trek (God, I wish the devs would watch some star trek episodes..the look is great, but the missions lack some of the qualities of Star Trek). As an example, the Squire of Trelane (but add some twists).
Player visits the planet, gets trapped/can't leave orbit, players beam down and have to deal with "Trelane" who will keep turning them into chickens and insulting them, he thinks you wear 14th century garb..etc
Players break a mirror object and then Trelane summons a bunch of napoleonic looking riflemen and the players must fight their way through to destroy whats behind it. Mission wraps up with Trelanes parents showing up and offering the player a unique reward for their troubles.
I could do this with just about any episode of TNG or TOG, convert it straight into the game's format. Now it's the devs turn.
I think the "Future of STO" article said something about an upcoming mission with Q in it, which might saitate some of your Trelane desires. I agree that missions could be more inspired, and have more interesting/wild plotlines. It'd require more unique 3D modelling and new textures to be made, so I'm guessing they're working on ironing out the bugs right now, and might add more interesting stuff later (God, I hope so...)