Here's just a few quick comments (some of which are implicit conclusions that Priah's observations contain):
1) Egypt gets tougher to use at higher levels, disproportionately so compared to other civs. Why? Well, 20% bonus wonder construction is only useful if you are at around the same tech level of the AI's. Above Prince, the AI will tech faster and your 20% production bonus may not help, since AI's will start wonders well before you throughout the early game.
2) Theodora is in the same boat. Enemy AI's will get religions faster at higher levels, and at Immortal and Deity, there's a serious risk you may not even found a religion at all, depending on the start. So her UA isn't as good at higher levels, either.
3) At higher levels, any strategy involving CS's can be a pain. Enemy AI's will quickly replace you as allies with CS's, and for this reason, Greece and Siam struggle a bit more than other civs on harder levels.
4) A few strategies that still work, more or less, at higher levels (I play on Emperor and occasionally Immortal):
- Persian 'Forever Golden' strategy; Chichen Itza appears late enough you stand a chance of getting it, and the GA works nicely to even boost your defensive capabilities.
- Monty; culture for kills, a great UU to help defend (assuming your start bias holds true and you roll jungle), and a UB that boosts population growth all help you to catch up across the board and eventually overtake the AI by the mid-game.
- Attila; Battering Rams if you want to take a nearby city, start with an extra tech to help you catch up in techs, pastures provide extra production, and an earlier, though less efficient, version of the Keshik. Attila is surprisingly versatile, especially with pastures providing a production boost.
- Korea; UU's designed to defend and extra science via the UA is incredibly useful.