I'm with Fagar as far as the Turks are concerned. They have a dynamic and exciting unit roster which fares well in all terrains (including the desert), and you literally have the opportunity to run rings around your opponents.

Turks in High era.

Other than that, I would definitely recommend the Armenians or Volga-Bulgarians for a real challenge.