[Fate]

More general than ages, here is a list of nations you DON'T want to start out playing against:

Ermor Ashen Empire (3rd age)
any underwater nation (especially LA R'lyeh)

mostly because they take a radically different strategy from normal to play. You probably also don't want to begin with EA or LA Mictlan because they have wacky dominion spread.

In Dom2 Ulm (now MA Ulm) was the most often suggested starting nation.

I'd agree that it is good to just pick random nations that look fun, play the first 15 turns, then switch if you run into trouble. If you find a nation you can start beating AI's with, try playing around with your god and strategy (maybe play a full game or two against an AI).

Welcome to DomIII, I hope you enjoy it.