What's a good starting nation for newbies?

[Archonsod]

EA Ulm is a good choice. Solid troops, magic isn't great spell wise, but you don't really need to rely on it. You just want enough to forge some decent magic items for your heroes, and a couple of mages for blade wind and your ready to rock. You only really need to concentrate on Earth magic (with perhaps a little fire or nature for a bit of diversity).

EA Sauromantia is another powerful nation. Magic is a lot more diverse, and the troops are also excellent. The massed archers trick works here too, especially with Androphag archers and their poisoned arrows.