MA Ulm is generally good for new players because it can be played without a deep understanding of the magic system. They have very good national troops which work reasonable well as a hammer if the new player just views everything the AI throws at them as nails.
Yomi, not so much. Yomi is a complicated nation which may well be looking at some rebalancing down the road.
The giant nations (Hinnom and its MA/LA counterparts, Jotanheim, Fomoria) are fairly good. If a player gives them a decent bless, they can send their sacred giants rampaging about merrily, and even without that they're usually pretty straightforward. I'd avoid Hinnomnomnom at the start, though.
Abysia and Marignon are straightforward to play as well; solid national troops plus strong Fire mages.
The Roman nations (Scelaria, Pythium) are also good starter nations: solid national troops in the legions, plus strong mages. They can give you a good base to start experimenting with some more advanced magical notions. I'd avoid the undead Roman nations, though; Ermor and Lemuria are at once too complicated and too simple to be a good choice when you're just starting.
There are a number of other newbie-friendly nations, but by the time you've messed about with all of these you should be comfortable just picking something at random.
[Edit: Man. How could I have forgotten Man? Man (particularly MA Man) may not be as "blunt" as Ulm, but it's still a very straightforward nation - longbows, spearmen, and knights - that's well-suited for a new player to the point where I'd be remiss not to mention them explicitly.]