First, though, do you know MOO2? It was done pretty darn well there.
One aspect would be to make every choice now there include a negative. For example, the Economics race modifiers would start at, say, -20, -10, etc rather than 0. That would give a player MORE picks to use elsewhere. To prevent uber-races, one might start the key stats at a minus number, or just make the changes more expensive.
Also, one might have fewer racial picks to "spend" at higher difficulties.
Perhaps the coolest such thing in MOO2 was "Uncreative." You got lots of bonus picks for choosing it, but it reduced your research rate but it also greatly reduced research in interesting ways. One was that it deleted things that could be researched.
In GCII, one analogous example would be no Xeno Farms. That is, the first tech above Basic Farms would be Intensive Farms, with the research costs to go from Basic to Intensive equal to the sum of the costs from Basic to Xeno to Intensive.
Another example in weapons might be no Phasers. One had to jump from Plasma to Dusruptors with the costs being all the costs summed that would have been there originally, just no intermediate techs along the way.
To make this last part as interesting as in MOO2, one would not know what items would be deleted until the galaxy layout was done, just as one does not know what bonus tiles one will have on the homeworld, or what PQ planets will be nearby.
You might never be able to research Trade, for example. Or, Democracy, or even Medium Hulls. You would have to trade/buy with other AIs or simply learn to do without for that game.