The way I understand the handicap right now, is that the AI receives certain bonuses to manu, tech, and money to help it remain competitive. I have no issues with handicaps, but what I often see with the strong handicaps is an alteration of the early game.
In Civ...this was the AI able to build all wonders. In Gal Civ, this would be a monstrously expanding AI or a crazy powerful early rush.
What I would like to try out for the AI, is a more scaled approach to handicaps. Start the AI on a roughly level playing field, but increase its bonuses over time (perhaps by tech phase, or simply by turn counter).
This would create a more organic approach, early game things are even. As the human uses more and more of its better gameplay to gain advantage the AI naturally counters with more bonuses. Further, as larger maps tend to leave to longer games, this would counteract some of the weakness the AI has on larger maps, which Frogboy listed as an area to attack.