[Morkilus]

Ulm's my favorite newbie nation since their low magic diversity (at least in the first two eras) focuses you on what to research, and a critical mass of heavy armor units is effective enough against indies. Their diversity of unit weaponry lets you learn the combat system and proper tactical placement (cavalry for flanking mages, high-prot + shields against arrows, flails vs chaff infantry). I'd say Niefelheim is a good step after that to learn how to use sacred units and build thugs, which are commanders that can take poorly defended provinces on their own.