One hint that took me a while to learn but really helps:
Always recruit mages. If n is the number of mages you have, the number you want is n + 1.
I would say play a little as nations like Ulm and Man, then try LA Ermor for a while (it gives you more of a feeling for how you can "break" the rules), then choose whichever nation sounds most interesting.
Don't worry about finishing games vs. the AI at first. If you are losing, or you aren't doing so well, restart as another nation/god (though it is hard to feel better than when you almost lose and come back).
This is all tenuous, because I am (relatively) new as well. All the nations are incredibly different, and you will probably find out what you're good at and bad at very quickly (not that that should affect how you play,

).
I hope you like the game.
