I played against her once on the Mediterranean Map, I chose random enemy A.I, on King and I was Arabia, Standard length. She was the best player, other than me, in the game. She had like 30 cities and was on a conquering spree around turn 150 when I finally got an army after her. I took her out easily enough, but that was one of the toughest fights I've had in Civ5. It took me time to get to her because I had to conquer my way through a defunct Bismark to get to her, but she at least matched me on techs and number of units.
It just seems to be random as to whether the A.I takes off, so to speak, or not. My analogy is: The A.I is like a spinning tire, sometimes in a game it just sort of spins staying in one place not doing much, but when it grips it's like an F1 car taking off and really grips.
I've played games on Prince and King that were tougher than the handful I've beat on the harder difficulties.