Barbs are definitely an issue. I have no idea what kind of combat bonus the AI gets against barbs now, but whatever it is, it needs to be cranked way up. I'm finding Deity AIs plagued by barbs camps way into the Medieval and Renaissance Eras. I'm totally fine with Deity AI units getting +10 or +15 combat strength against barbs if that's what it takes for the AI to develop properly. Barbs are in the game to challenge the player, not to cripple the AIs. I've also noticed that in addition to not expanding enough, the AI is having trouble growing the cities that it does have. AI cities should pretty much always grow faster than mine on Deity, but I'm seeing size 6 and size 7 AI capitals while I'm at size 10. I'm guessing the housing system is the problem here. Again, I'm fine with the AI getting +4 housing in the capital and +2 housing in all other cities, or even more if necessary. I just want an opponent that can deliver a reasonable lategame challenge.