Here's a simple variant game start idea that once I get a regular group to play with I may try out. Rather than starting with a capital you place a Scout in one of the four starting squares then place a second Scout and your army in the squares on the outskirts of that.
Play proceeds as normal with the following slight change. When you build your first city (which may be on the first turn) you build your capital and get any start of game capital bonuses. So Egyptians would get a random Ancient wonder at this point and the Chinese Capital would be built with walls. Plus you gain the trade from the squares around your capital when it is built and again the the trade phase.
Basically this could play out exactly the same as a normal game with everyone building their capital on their first turn, but people could choose to hold off for a turn or two to explore and see if there are any nice tiles nearby. Of course by doing so they are accepting the fact that they can't build or research (as they have no trade) while they have no capital.
What does anyone think?