Carthage once you get by the first 50 or so years and not only take sicily but also put a decent army into Italy to annoy the Romans.The Carthagenians are badly out-classed troop wise early on but more than make up for it later.

Scythia are fun to play with as long as you are good at micro-managing horse-archers.If you master this fine art then no one can readily stand against you.Slip up and it's off to the knackers yard for all your horsie units.