Most difficult nation

[General Tacticus]

Starting position can make a lot of difference. If you mean conquer the World in the World Map scenario, for example, then Mictlan has a very good starting position, while Ulm's is really awful. In fact, I spent weeks trying to find a way to survive it against impossible AI's, before finally finding a strategy that made it possible... whereas my Mictlan attempt succeeded on the first try. And yet I consider Ulm far easier to play than Mictlan.

I would say that nations with no access to good heavy infantry are harder to play (Mictlan and Pangea come to mind), but that may be my play style...