1) Balanced options/models. An imbalanced choice (corner solution) should be regarded as a fun experiment, not the best way to play a game.
2) Strong governors. Reduce micromanaging without taking away control from the player. Otherwise he might just as well watch the governor play the game for him. GC2 does this quite well already.
3) Strong diplomacy. It should be about more than just two tests:
a) am I stronger?
how does my roll compare to me liking him?
-> War it is.
4) A polish. A game has to look and feel finished. You can see this in the details such as diplomatic texts. Having the AI grovel because it attacked you and got his face punched in is gratifying and entertaining (which is what it's all about).
5) A game tailored to the gamers. Stardock does this unlike any other developer I've seen by launching scores of updates on the AI to cope with player reactions to the AI. One such addition was the AI declaring war when you stacked transports along the border.
6) A strong AI. It's less fun to see the Yor declare war on you when you've got transports near him because the Drengin declared war on you and has his planets close with the Yor. It's understandable nevertheless.
7) A fair AI. The AI should play fair on a decent number of difficulty settings and should put up enough of a fight to make it fun. GC2 succeeds in this for many players I think.
8) Balanced victory conditions. In some games, one victory condition becomes so dominant, it impoverishes the game. Technology should be about more than 'Alright, I invented hammers! What new and exotic way did I find to kill my neighbors?' for example.