There are a ton of great ideas so far in this thiread. Super impressed!
As for my own suggestions, (the ones I didn't see covered in this thread):
1) Dimplomatic AI
AI will try to ally, create good relations, with other players in a strategic manor. They won't just give you missions and ally with you if you complete them. They will try to build up with those players who are stronger, enemies with their enemy or in a strategic location (ie. on the other side of their enemy).
If under duress, AI will try to negotiate peace or cease fires with a winning opponent, but only to an extent (not compromise their position so they can't ever win). And if all else fails, instead of quitting the game, they might offer surrender with conditions (ie. a vassal state, control over planets without blood shed, or eternal alliance).
If there is one very strong opponent (alliance or individual) a few weaker players may try to negotiate a war pact where they all agree to attack an opponent together. This may involve some negotiations, like control of planets, delivery of resources, or ships. This could also be done less as an alliance and more of a back room deal (ie. attack my enemy X and I'll pay you X resources/minute until the deal is terminated).
2) Random Events (adding to above)
It would be really neat if random events occured like missions that pitted players against each other (or brought them together). This could be done in a few ways. One could be a type of artifact. If discovered on a planet it would be an ancient relic that has enormous significance to another player's populous. If that player acquires said planet, then they get some kind of reward (capital ship spawn, resources, +5% culture spread rate etc). Now this could be done through military means (conquering planet) or diplomatic (trading planet for something). This might also work as a type of alternative to victory a la new risk board game style. These random events could be missioned based or something, where if you complete 3/5 missions you win (the more customizable the win options the better.. especially for online play).
3) Exotic Resources (adding to above)
Have new types of resources spread throughout the map (colonizable or non colonizable) that act as modifyers. So for example, if resource X is in an astroid, and you send a colony ship to set up resource extractor, then that extractor will start trading with trade ports. Whever those trade ships trade at, then those gravity wells will receive a bonus. It could be bonus to mining, bonus to population growth, population max, ship creation speed etc.
This could be done in a nother way too, in that special upgrades or ships might require 3 special resources or something. Maybe the most powerful espionage missions would require that you control certain resources, or perhaps just a certain number of them. (putonium to sabotage a space station)
4) Generals, Governors and Governments
Generals: Can be added to a capital ship, which gives fleet bonuses. To make it more interesting you could have different types of generals (offensive to boost attack type attributes, defensive to boost hitpoints, electronic to boost antimatter, engineer to boost speed etc). These could be trained at special quarters (a new structure), out of starbases (or an upgrade could be added to starbases that have to be researched then purchased), capital planets or perhaps recruited from the black market. Bidding wars for mercenary generals! I'd prefer a mix of upgrade for star base and black market mercenaries.
How to get the general from the market to the desired ship. Perhaps the mercenaries come with a ship that spawns on your capital. Also, perhaps to access this black market you would have to upgrade a starbase with a mercenary bay or something. Then the ship would just spawn there, or the general would appear in that star base and then you could transfer them to any capital ship you like.
Governors: are similar to Generals but non militaristic. They could be added to planets (or starbases?) in order to boost specific qualities. They could increase production speeds, mineral outputs, taxes, trade, culture spread.. etc.
Perhaps Governors are more dynamic in that you give them orders (reduce mineral output and increase taxes) so that they are more of a specilizing character rather than a straight boost. It's an either or scenario. Lower crystal production to increase metal output for example. Slow population growth but increase max population. And these orders can be changed whenever you want, but perhaps with a timer penalty.
Governments: controlled at the capital and give different effects for the entire empire. This could be done in multiple ways. One could be a trade off type fashion that you enact a government ( chosen from a list) and each one has specific strengths and weaknesses. Consumer Democracy increases happiness (max population and growth) and trade, but gives negative effects when at war. Theocratic Democracy increases happiness(max population and growth) and culture spread rate, but gives negative effects when at war. Theocratic Facism decreases happiness (max population and growth), but increases culture spread rate and gives boosts while at war (increased damage).
Another way to do it is through a type of research, where you can only pick one path and then increase the effectiveness of that government through research. To change to another government would require a revolution (with negative penalties until it is over). Perhaps resources, or you might have to quell uprisings on planets.
5) Dual Espionage
I'd like to see espionage and counter espionage aspects added to the game where you can focus on one or the other or somewhere in between. This could be done through research, where the implementation is done through the actual map.
I'm not sure what I think about a unit based spy system where you have to actually send in a spy ship to a system. I'd rather this be automatic and the actual spying process be done on a macro level. ie. you have a list of the spies you have hired and then you give them missions. These missions could then have different levels of depth with different probabilities of success. This way you could tell your spy to sabotage any building in this empire. This would have a higher probablity of success than say, sabotage this specific building in this specific gravity well.
Also, leveling up spies through xp would be neat. Perhaps customizing them as they level up like a cap ship. So better as sabotage (blowing up ships), or intelligence (revealing information), or unrest (disrupting economics or planet growth etc).
(now that I think about it, this is similar to the imperium galactica II style of espionage if anyone else remembers that, I remember it being pretty sweet. Corect me if I'm wrong haha)
6) Win Conditions
This one I'm a bit torn on. There are things like capture the flag, and king of the hill that would be good to implement, but they still seem very militaristic.
We could go the route of age of empires and add a wonder win system (build one and win after a counter). We could do a Rise of Nations style where you have to build more than your enemy by X amount of points.
I'm trying to think of ways, though, to win on economics or culture or diplomacy. The random world events/missions could hit many of these in different ways. ie. become #1 in Credits, Metal and Crystal production for 5 minutes. To avoid someone winning in the first 5 minutes, dish out the missions 10 minutes into the game or something. A mission for culture could be "take over 5 planets via culture spread". Diplomacy could be "create an alliance with 3 or more players and succesfully defeat an opponent/conquer 10 planets/set up trade between 10 colonies from each player/share exotic resources with all players in the alliance". Something like Diplomacy missions might seem too easy, but remember missions are for only one person. So you'd have to sneakily make a 3 person alliance without the allies knowing why.
Also, giving the choice to players as to how the conditions are met before the game starts would help the online community (and offline as well to some extent). For example, you could choose between successfully completing 10 missions, 5 missions, 3 missions, 2 missions or 1 mission. If it's a wonder type victory, let the players decide how many wonders and how long of a timer. Perhaps add in some other quick win objectives like 75% of colonizable planets occupied (which can be changed to any number).
That's all I have for now. Which turned out to be a lot more than I expected. Any feedback on these I'd like to hear too!