Base (or the core) of the game feels really promising, but things that are built upon it lack depth. The game needs more things to achieve, accomplish, and affect to the game world, itself. Especially, anything related to diplomacy, diplomatic events, and rules. And the combat, oh, the combat.
Bug fixes isn't what Stellaris needs the most atm, since it runs pretty well (at least for me). Only issue I've had pretty much was one war where my ally got declared war upon, but the stronger enemy attacked my main planet with it's full force as it's first thing to do, and my ally meanwhile did nothing; no assisting, no attacking the enemy. His ships just happily sat there on his terrain. Meanwhile, the planet of mine got bombarded down, and the enemy tried to conquer it several times with it's ground forces, but didn't even come close succeeding. The fleet was just way too strong for me to eliminate from the orbit of the main planet. The war also never ended because for some reason the war score just sat there static at 30'ish something, despite the enemy barricading my main planet with it's fleet (and my ally doing nothing). I had to start over, because I couldn't eliminate the fleet, and the war wasn't going to end, so I suppose war score calculations and war rules needs some tweaking, but that's pretty much it.
Diplomacy, events, and combat really need much more meat to them, though. Not just small tweaks, but more like major additions; new ways to play around with things, with new possibilities to accomplish things (and be rewarded for them). I don't need 10 times more samey pop-up windows with more stories that just small boost to A, B, or C -type research, but major additions to the game's core and rule system itself. Things to do in the game is just a bit narrow and thin side right now, and it starts to drag on quite a bit after the promising beginning.
Espionage/sabotage would be cool. For example espionage tech, sabotage relations, fleet, wormholes etc.; and perhaps either long time to accomplish bigger missions, or spend considerable chunk of influence (or other reso) to complete such action. Success rate of these actions should also be tied to something (racial, resources etc.), so that you have choice to go into espionage/sabotage direction, but similarly you have lesser chance to play it the other way (for example, if you invest into esp/sabo, then that's away from your war investment). Other non-directly select-able events (random, which occur more often when you have those extra credits hanging on your balance) to spend extra energy credits, influence, or minerals would also be welcome; granting you perhaps such things which give you something which you can't directly buy from Starport. Mercenaries with special weapons or ships, which, come in lesser quantities, but give you an edge over your current tech level ships? Occurring more often for those with certain perks (charismatic), perhaps?
"Influence" is a bit lame right now, as well. You gain it through a few special buildings or declaring rivalries (which lower a relations between you and player X), and you spend it on only a few things; mostly recruiting leaders, or using edics. I'd like to see more use for influence (or make a separate variable called "prestige" - representing how well you're "respected" throughout the universe by your past history, wars etc.), and more ways to gain it. For example, winning wars could be rewarded with influence points, more points of winning a defensive than offensive war. You could then use influence on new political options, or perhaps upgrading your current leader, scientist, or general with a new extra perk, recruit a specific powerful mercenaries, whatever, with a cost of influence points (or "prestige"). Perhaps losing an offensive war could also make you lose influence (or prestige), while losing a defensive war would have zero effect on influence points (or "prestige").
Those are just a few several dumb examples of many ways to boost important factors of the game, which could be added to make Stellaris more vibrant to play. More things to do, more ways to do things; tied to your racial and empire's backgrounds preferably, so, that those things would matter more than at the moment. At the moment, I think the races play bit too similarly, and thus are bit faceless. I hope this changes, especially if they add more "meat" to the politics.
I'd say this is the most interesting and promising Paradox title to come out yet, and the most incomplete one as vanilla. I really want to like this game, but it just falls a bit short as it is for now... still quite good, but could be damn good, so why the hell not?