Right now, Galciv3 has essentially no expansion penalties. Maintenance costs are trivial, especially for new colonies, and your existing colonies suffer no ill effects from the expansion of your empire. The only thing you lose from expanding is the cost of the construction ship. Thus, a civilization's growth will follow an extreme exponential curve.
The consequence of this in the gameplay is that the early game is everything. If you grab 1-2 more colonies early, your expansion later will be accelerated, meaning that it will take extreme circumstances for an player behind you to catch up. The complaints about map balance bear this out - a map that hands one player more nearby planets lets them start their exponential buildup sooner, making it nearly impossible to stop them. In these conditions, reaching a challenging midgame scenario requires that players expand at roughly the same rate - which is improbable given that small variations in the first wave of expansion can lead to seriously different expansion rates in the second wave (by "second wave" I mean the wave produced when the initial colonies get their own shipyards).
Expansion penalties have been implemented in 4X games in order to slow this exponential runaway factor - with the goal that good play will still be rewarded, but comebacks can be achieved through superior play later on. This serves to keep the game interesting both for those who did well, and those who did poorly. This has been done in several ways - Endless Space and Civ V penalized happiness, GalCiv2 had a fairly stiff base maintenance cost on colonies, and Civ IV had increasing maintenance costs based on city count and distance from capitol. I like how the Civ IV system keeps the decision on whether to expand interesting from start to finish - since cities get more expensive as you add more, it generally requires thought as to whether you can afford more.
However, GalCiv3 has a lot more planets than CivIV has cities, so perhaps that system isn't suited to this particular game. Another option would simply be increasing colony maintenance back to around GalCiv2 levels. Whether this would work depends on how readily one can generate wealth. This would certainly be worth testing in the beta - it would probably take a good deal of iteration to find effective values, if they exist.
Any other ideas on how to keep early expansion from deciding a match?