I completely agree with Morahed. I never tried praetorians but the immortals are cheap enough to build in numbers and rock with the bonus against axemen and archers. Spearmen can be a problem but if you manage to get your units upgraded, they are a lesser problem. Also, the immortals can do an awesome job pillaging the enemy's resources.
Another leader I'd like to mention is Genghis Khan. Nobody mentioned him so far but he plain rocks. You'll say Keshiks come too late in the game. You may say they are too expensive and they don't offer advantages. You may say they only have 6 strength - nothing more than a swordsman.
I tried them out and was astounded by their efficiency. They come just in the time when you will have build a couple of cities with good production so you can start massing them without bothering to stop the production of military units because you need civil buildings or workers which is the problem with the early units.
Second, use the Ger
Nothing, I mean nothing can stop a stack of Keshiks who came out of a city which has barracks, a ger and Theocracy (very easy to get with a prophet). Imagine you get the imperialistic bonus to get more experience to the units built in your cities.
Those upgraded monsters devastate spearmen behind city defenses.
The imperialistic bonus does help to get an advantage in the early claiming of territory and still not get slowed by producing a settler. The advantage isn't that great but it helps.
Genghis is also aggressive - so you can get some early protection with good axes and spears while expanding.
By the time your neighbours get macemen (and worse - pikes), they will find out they are a part of the huge Mongolian Empire