Just my personal experience, but the early rushers like Ghengis, Monty and Atilla have never runaway and won in any game I've played, that I can ever remember. The AI just doesn't have the smarts to win that kind of ploy, I guess. They just let their civs go to hell and focus 100% on military, and when you stop them, they just get into the same rut of surrender, recover, attack, surrender, etc., until you or somebody else puts them out of their misery. No balance, one trick ponies, losers all. When you look at their cities and lands afterwards, the neglect is often pathetic.
Never seen Dido do squat yet, couple times she was a mid-level player, but never a threat. Same with Theodora. They're like female Washington's.