I would suggest MA Ashdod or EA Niefelheim. They're some of the strongest nations in the game, have powerful magic, armies, sacreds, and recruitable SCs... and can be played decently in multiple ways, so you can experiment with them a bit. These are fairly straightforward power nations, so not too much thinking out of the box is necessary. The suggestions of MA Man and MA Ulm are given often, but I've found that players who start out with these nations end up getting the mistaken impression that they're rather strong, when in reality these are some of the weakest nations in the game
As far as settings go - I would suggest leaving most settings at default, with the possible exceptions of magic research and random events. For your first few games, it will make things a lot easier on you to play with easy research and few random events. Few random events lets you gain more points by taking misfortune scales without too much worry, and will prevent you from having to do as much backfield cleanup. I'd also suggest playing on a map that's thin and long, with one easy AI. This will provide a funneling effect making it harder for the AI to maneuver armies around you, so you'll need fewer effective armies and not need to worry as much about defending your borders. In fact I'll provide you with an example map. You can NOT put more than one AI on this map. You'll have to unzip it and put the contents into your "\dominions3\maps" directory. Unless you have windows 7, and then it might be in someplace trickier to find.
One last suggestion - when you start out, try playing against only human nations. Like tien chi, man, ulm, vanheim, etc. Some of the other nations, like say abysia, have special abilities that can make it a lot harder to deal with them if you're not prepared, and you probably want to get a handle on how things like magic and forging work before trying to fight them.