The vast majority of feedback revolves around PvP issues, balance and content alike. While I certainly agree that the PvP environments should improve, please do not neglect PvE. Most PvP-players see PvE as a necessary evil to get equipment, and I don't want them to cry so loud that the devs can't hear those of us who actually like the PvE aspects of the game.
There are a number of ways to improve our PvE-experience. I'll leave out missions and episodes, because we will already get weekly episodes (soon), and they are an entirely different subject. I want to talk about PvE without a linear story.
Exploration
As has already been stated by some devs, exploration is not really the way it should be right now. It feels too much like being put in a shoebox and too little like actually exploring
space. This is also due to a lack of diverse mission designs - bases and planets always have a similar layout, as do "secure the system" missions. So, the most important thing would be to introduce
way more missions that can be done during an exploration. Because the shows give a nearly endless supply for ideas, I won't even get started with suggestions. You could pick any TV episode and and turn it into something for the exploration-missions.
Incentive
Many - mostly PvP-oriented or casual players - fear that STO might get turned into a gear-driven MMO. Although this is a reasonable concern when looking at other games of the genre, the current lack of interesting gear and the limited ways to acquire them (marks) severly destroys any incentive to do PvE missions for loot. This is bad because it limits PvE to mission-type settings, with a certain task you have to complete to gain marks/emblems/currency x. So we cannot have persistent PvE zones untill we introduce a wider variety of gears or other items which can be found in these zones.
Another issue with marks as reward is also that you can only do the missions once a day. If I do them more frequently, I am basically wasting my time.
I heard dstahl say in another post that he is not happy with the current gears either. When the devs take a look at this issue, I'd be more than happy if they could think about PvE zones as well (maybe gear that is especially effective against Nausicaan/Undine/.. shields, etc.).
Enemy variety
Currently, every enemy, space or ground, can be defeated more or less in the same way. I believe this is mainly due to a lack of abilites - which is not unusual in young MMOs. So this is not really a complaint, but more like a reminder not to forget to make new BO abilites, which should result in more diverse and challenging enemies (as long as they use those abilites, of course).
In fact, lower tier PvE seems a lot more challenging, especially because enemies use a lot of powers which the player cannot acquire at that stage (Gorn warp plasma, Nausicaan energy siphons, etc).
Persistent PvE
I believe this has already been an option in a survey, but apparently, it didn't rank high.
Every roleplayer should know what a dungeon is, and this is exactly what STO lacks right now. We have very immersive, show-like missions and episodes, difficult and engaging STFs and fleet actions which require several players to work together, but no environment where a player could just zone in on his own and do some hack and slay.
One might say that the DSEs should be enough, but they are quite different. First, there is no real incentive (see above) to do them, and second, you can AFK them and let others do the work. There is also no real strategy involved when several players just fire away on a Borg cubus.
So, what I would like to see are instanced areas which I can enter alone or with friends. There could be different "levels" (possibly connected by transwarp gates) to these areas, maze-like gas clouds which block certain ways, or just a large single area. Enough possible designs should come to mind.
I would also like to see "boss" enemies like in STFs in these zones, which should require real strategy and maybe even a team to bring down.
A small idea: The Arena
While doing the Klingon "tutorial" on tribble today, I was saddened that I couldn't fight any more Klingons after defeating my 3 bridge officers. I really wanted to try some melee combos, but I didn't really feel like jumping into my BoP and flying to a ground fleet action just to search some lone Fed to punch around.
So I wondered, what about a similar arena-like setting, where you could fight enemy after enemy one on one, until you beat the arena champion - if you advance that far - and claim a neat prize. Depending on the hopeful variety of enemies, this could be really entertaining (I saw some new melee weapons in the Klingon tutorial. I hope we get these soon, too!). This arena should take place in a neutral environment so Federation and Klingon players alike could have some fun. Drozana station, probably?
Such a PvE mode would also be perfect to introduce new accolades and dailies, so it fits well into the current system. A hall of fame would be nice, too!

PS: I'm sorry about the wall of text.
Comments
But not every mission-type should be given to exploration, most of the scenarios found in ST movies or shows are complex enough for a regular mission, which I'd prefer.