Multiplayer conquest would be awesome (the awesomest thing ever), but as zarkonnen said, implementing it like conquest currently works would mean spectating a lot of battles. So here's an idea of how it could work in a more player-friendly way.
Make it partially turn-based.
The game would be divided in turns, in three parts each. Planning, Action, Battle.
First, players are on the conquest map, and the game is paused. This is the time for planning and giving orders to fleets, queuing up ships in shipyards, spying around, and designing stuff. When all players press a "ready" button, the game progress to the next part. In order for this part not to last forever because someone is busy on the design board, there could be a max amount of time (most likely a few minutes), maybe set by the player creating the game, and maybe increasing as players empires get bigger and have bigger fleets to manage.
The second part is unpaused, and stuff happens. Fleets move, spy actions launched during the preceding phase happen, and any battle which needs to happen is added to a queue. Giving orders on the fly is still possible. After a set amount of time, or enough battles queued per player, the game progress to the next part. The speed at which this part happen (normal, fast, superfast) could be voted at the end of the first part when players mark they're ready, so they don't all spend forever waiting on things to be built.
The third part is where the battles happen. The game would schedule the order of battles so as many battles as possible would happen at the same time, each involving a different player, or two if it is a PVP battle. Once a player has done all the battles he is involved in, he would be back on the map, able to give orders and design things, but the first part and it's timer would resume only when all players have finished combat. By having players not spectating battles they are not involved in, we avoid some "spying by game design" which would not be possible on AI empires. All bonuses gained form battles against monsters would be gained after the corresponding player has finished his battles.
The only thing that is not obvious is, what happens to cities when they are attacked, like for the ongoing construction of ships, income, and the battle only happens later. Does it keep going until the battle, which would allow stuff to be built before the battle happens (and fleets to come help defend or attack the city after battle has been scheduled), or does it stop until the battle happens? If it keeps going and the player loses the city, he'll have some extra income. If it does not, he loses income. Which would allow for strategies like attacking a city with a cheap gunship just to paralyze the enemy economy. So i'd say the cities should keep going. It'll make the game slightly different form singleplayer conquest though.
Oh and please, co-op. Having two or more players in the same empire, maybe even the possibility for players which empires are destroyed to join another empire (or restart in the next revolting city for that matter) would be great. that'll make the decision making part faster too, and allow for either more battles to happen at once or having multiple players controlling a side (which could be OP though).
Relative to having multiple players on the same side of the battle, maybe we could set some ships (which number would be like half of ships on your side in order not to be OP) to use AI when in battle. That would cut a lot of micromanagement needed on hips with short range weapons (ram, saw, flamethrower, grenades, ...) or needing a lot of positioning in general. That would cut a lot of tedium zarkonnen does not like and at the same time allow a side in a battle with fewer players than the other to stay competitive (the other side would have a lower cap on the number of ships using AI because of it's higher number of players).
Anyway that's my 2 cents on how to make things work.
from what i understand, multiplayer conquest is a much-requested feature that probably wont happen, due to the fact that it would take a complete re-write to the game to implement. maybe one day :P
From what i understood from zarkonnen's posts, it's more of a game design problem than a programming one. But ok. I'm just showing a way it could work if he decides to develop multiplayer conquest.
Also, about map gen :
Cities have 2 main parameters, their size (shipyard and income) and their tech. In MP, there would be more starting cities for human players, which if they were generated as they are now would have a size depending on the difficulty and no tech.
For the size, having it depend of the difficulty is fine, but as neighboring cities are small and further cities have increasing size (which works fine in singleplayer), with enough player cities, most of the map would be reduced to small cities. Maybe having city sizes be randomized outside of starting cities would be better (and even in SP ; There wouldn't be only huge cities on most of the map which would be maybe more balanced and definitely more interesting, especially as the cities capable of building large ships in reasonable time would be lower).
For the tech, the problem with no tech in starting cities in mp would be that other players starting cities would be uninteresting to conquer and as the number of players increase, the amount of available tech decreases. So it would be needed for starting cities to have a tech. That would also give potential starting strategies at the beginning of the game.
Finally, for balance, maybe starting cities should all have the same number of monster nests (and all empty at the beginning). Not sure about outside connections as having road or sea acess or not could make for interesting strategies.
I like your balancing suggestions for MP Conquest- it makes plenty of sense. The phases system is really cool, and I think it would work out (although I think the action stage should at least have the option to be time triggered instead of defined by a certain amount of battles, to avoid fleets getting tied up in games of battle-chicken)