[dirtywick]

Arco is a good starting nation as someone stated. They have a variety of magic, stealth, flying, and regular troops. I also think Machaka is a great nation to start with, they have a good path variety giving you a lot of strategy options and the ability to build stealthy armies. And actually I think MA Ermor would be a good starter nation.