If we do start something like this, I'm in favor of strange variants like the Realms Beyond folks tend to host(though then someone has to come up the variants as well
. http://realmsbeyond.net/civ/civ4-tournamentgamelist.html
They tend to be a bit longer/more spaced out as well(one every month or two).
Imagine, a game where you can only build tier II+ units/buildings on your home planet(with perhaps the exception of adv factories and fabs).
Or perhaps a bonus ship game. Beat the game without ever building a fighter, bomber or cruiser.
A no hop game(can't take a planet not connected to another planet you own).
The possibilities are endless.
On the randomness side, the easiest way is have everyone start from a posted save, since almost everything has been generated by that point and no one can screw things up by picking the wrong options by accident.