More internal diplomacy, for example a tax rate for your empire, maybe per system, or even per planet.
Certain laws you could pass which modify happinces, troop morale, production etc.
Ministers with different personalities, and assasinable (is that a word?), like in MOO (no, not the cow, the game
)
A non-tiled combat map, let the ships go wherever there is room.
Ground combat, like there is space combat.
Precombat fase, where you can deploy your satellites/mines/bases.
Scriptable AI, like SJ said, in pseudocode for example.
Naive primitive population on planets which you could subdue, or somehow recruit to fight for you (different combat modifiers), or sell as slaves throughout your empire.
And some "famous" desires:
Components which generate research/intel points
Cloakable planets
Racial traits should be kept once an alien race is captured.
Different ("working") more usefull emmisive armor