Fire Main wrecks others from server opening up to the point where you can change class. I hate fire main early in game, as they always ruin my chances of leading in the ST. You'll know what I'm talking about once you face them, they don't even have to be OP, they'd just chip your hp away and ruins your ST.
At 60, switch to Lightning Main. IMPORTANT: At this point, you should have saved up kurenai frags, 4 star of her with skillbroken chase would let you dominate your sage bracket.
Sasuke - Kurenai - LM
X- Iruka - X Root of Warrior team
You can stay as LM should you decide to focus drawing from GNW treasure. By the 2nd month, you should have at least 200+ seals provided you're active (try to reach 300 seals for the rebate).. If lucky, you may even get Kushimaru and Jinpachi, which will again let you win 99% of your sage battles assuming you've frozen your level at 70 and has good lead in terms of power. The 3rd ninja would be Edo Sasori.
Water main is for mid to late game. Your instances will be slow as hell if you start with azure fang, but if you don't mind spending hours daily, then you can start with AF.
Earth main is mostly for late game, can be used mid-game, but you're way too vulnerable to hard cc teams with limited ninja pool to synergize with.

Now if you're a heavy spender, then none of the above really does matter. Depending on which premium ninja you're aiming for, then you can decide which main could serve useful.


Useful F2P Ninjas you should get early on:
Kurenai (an S+ ninja, just below god tier.. she has to be fully skillbroken first though.. DON'T miss out on her! found in elite instance and ARENA shop)
Shikaku Nara (really good early on, knowing most people will be using those other common ninjas)
Hinata (back then, Kimimaro was favored, but then Hinata is more versatile and shuts down blitz teams)
GNW Sakura (offers great survivability, most people just can't burst her early on and pretty much the ninja that always stands last)
Kabuto (great healer, but the nerf just made him less appealing.. can still be used with the double-target healing/cleansing)


P.S.
I disagree with people saying level-freezing is pointless.
That DEPENDS on your server cluster. You said you're looking for a newly-opened server, then most of your sage will be set according to your level bracket.
The early servers, like the very old ones aren't conducive to level-freezing, as their low level players get matched with 5x their power.
I've frozen my level for almost 2 months, so glad I did. So fkn glad.
I regret when I got impatient and leveled to 75, and my usual 15+ sage streaks now went down below 10. There's just too many monsters in my bracket now.
So if you want to be on top 5 for quite some time, FREEZE at 70 (where you unlock most treasures). As in completely freeze.
Save the Advanced Refine Runes you get from sage, even try wait for the rebate and refine 500x.