The two methods are quite different, especially in a game like Civ. The handicap should always be imposed through penalties, never through bonuses and one side (either players or AI) should always be at the baseline, never above that point.Giving out penalties at lower levels is the same as giving out bonuses at higher levels. Don't ever expect to fight an amazing AI in a game like Civ. It won't happen, it's too complex of a game.
Take science for example. A science penalty will make research projects take longer, this can be overcome by putting more effort into research at the expense of something else (production, gold income, etc). A science bonus will make research projects easier, putting more effort into research at the expense of something else (production, gold income, etc) will result in accelerated research. In Civ this translates to things like having tanks on the battlefield in 1400AD.
Penalize the player at higher levels, penalize the AI at lower levels and you'll preserve that game balance and the pace of the game. Give either of them a bonus and you run the risk of breaking things. I dislike the stock handicaps in Civ 4 because higher levels tend to result in shorter games (fewer turns) that take longer (more units for the AI to move back and forth for no reason).