Cheats afforded the AI in balanced mode:
2x as good at attacking Barbarians as you.
Unit supply cost at 20% (!!!) of you
Unit upgrade cost at 50%
AI inflation rate at 80%
So now look at your economy and you do the math. The cheats become huge later on- maybe the AI can't handle all the wealth?

Supply cost is irrelevant, that the max number of units, the AI will get broke first from units upkeep cost. I think the problem is the early game the old ways of setting difficulties does not seem to apply directly to CIV5, I think they tried to adjust them but not enough the early game is just stacked against the AI as their bonus is not enough to make a diffrence. In CIV4 they made a diffrence beacuse the quantity of units was higher in CIV5 every unit count. So 20 units in civ4 with bonus of 10% gave 22 units. So one more. In CIV5 with 15% you still get 1 unit more in the early game, it will make a diffrence later when you do have 8-9 units. I think the bonuses might need to be as high as 50% for training and same with upkeep to compensate for the fewer units in CIV5. Thats on KING, deity should be maybe 100%.
Lets look at King CIV5 compared with CIV4 Monarch bonuses.
CIV5
-1 bonus defender.
-Player 33% bonus against barbarians vs 60% for AI.
-20% bonus to worker speed
-90% of unhappiness (10%) Bonus
-90 Growth needed (10%)
-85% Unit training cost (15%) Bonus
-85% Building build cost (15%) Bonus
-85% Wonder build cost (15%) Bonus
-85% of Building Mainteance cost (15%) Bonus
-85% of Unit upkeep cost (15%) Bonus
-30% Bonus to Supply (Almost irrelevant as money will run out before this limit)
-50% Less upgrade cost (Really the only bonus that worth a lot, and this is the same on all levels)
-Free tech Pottery
-Same cost of research
CIV 4 Monarch Level
1 Defender + 1 Worker free.
Player 0% bonus against Barbarians AI 40% (Player get 0% bonus in CIV4)
3 Health bonus vs 2 Health for player (50% Bonus early game) Not comparable
5 Happy vs 4 Happy (25% Bonus early game) Not comparable
-90% food required for growth (10% Bonus)
-90% Unit training cost (10%) Bonus
-90% Building build cost (10%) Bonus
-90% Wonder build cost (10%) Bonus
-90% of Unit upkeep cost (10%) Bonus
-25% Supply cost (This was not factor in CIV4)
-50% Less upgrade cost
-Free tech Archery
-15% diffrence in tech cost
Seeing this and starting to apply these bonuses to the lower values in the early game of CIV5 they are almost insignificant in the early game these bonuses are way to small the 85% upkeep cost in CIV5 means like 1 or 2 units more.
The AI needs higher bonuses in the early game to compete with a player, atleast a free workers and lower upkeep cost, I also think they should have a higher happiness bonus. I also think the 50% upgrade cost is to high. This is an area where the player has a huge advantage as the player can pick and chose and have more experienced troops.
I also think the 15% bonus to training and construction is to small for the early game. Giving the AI pottery instead of Archery is another interesting diffrence.
So king in CIV5 is not Monarch in CIV4 its much easier in my opinoin. And lower setting are laughable in civ5 they AI actually pay more than the player.
The difficulties are out of wack and as the first poster say the game is set to be way easier on earlier difficulties. Also the Barbarian bonus should go to make them a threat.
Time to up the level in CIV5 from civ4 and/or modify the files so the AI has a chance in the early game.