I think that with Alexander they went a little bit too far. You have three factors against you - the standard Deity bonuses of the AI (especially in combat), extremely low number of turns (forces you to rush like crazy and conquer I think almost one city per turn) and you have to build/buy quite a lot of settlers (was it 12?) and found cities with them, which also takes a lot of time and you can actually lose just by not being able to move the last settler to a suitable tile in time.
I don't understand why did they have to put the city founding part to the conditions.
As I said, I don't have this one, it's my only missing achievement from all scenarious, and I'm not going to give it another try, because it's really tedious for me and not fun at all - and fun is what games should be about
I don't really remember Path to Nirvana, but I'm sure I got it on deity on the first try (I mean first try on deity, before that I finished it as the other sides on lower diffs).
Nubia wasn't hard either and regardless what others said here, I think I won it on Deity as Egypt and I didn't really see any additional problems (maybe I was just lucky).
Vikings was quite easy with the right civ. I don't remember which one it was, but it was the closest to the British Isles (but not the one that starts on the europian main continent). And I got much more points than I needed.
Poland was also very easy, again with the right civ. This time you must pick the one that is closest to the city states that you must protect. Because that allows you to concentrate your units in one area.
In the end, I was really surprised how easy most of the Deity scenarious were, compared to Alexander.