That is the big variant.
I was thinking more of a small variant like this (still lots of work):
Normal Civ4 C2C playing and engine.
A simple server (it needs to run all the time but the load is very limited).
The first time a game connects to the server, it gets assigned a position in space.
Some global information about the map and its players is transmitted and updated when it changes.
When you get to the later parts of the game you can start exploring space in a screen similar to what Hydro described here earlier and the game then starts questioning the server about planets that are in the area that you explore. You first only get limited information about each planet but you can send an exploration mission to find out more.
Interaction between games only happens as missions, each with their own leader and if they appear in other games then as AI and you only might get messages or events now and then.
Missions might be invasions, trade attempts, production colonies and the like.
One difficult thing to do would be how to deal with missions in which the counterpart game is not played in that time or not a lot.
While that is still a big undertaking, it is mostly so on the concept, coding and AI part and not a lot on the graphics part.