The hardest rated faction according to the game is Western Roman Empire, but I find that if you make some smart decisions early, by turn 20 you can whip your flabby, decadent collection of no-goods back into a superpower, and its all over at that point except for the Triumph parades.

I haven't tried anyone else yet, though I suspect the Goths would be rather difficult, because they have to deal with both the Roman empires, as well as being directly in the path of several invading hordes.