As usual, or azure fang or midnight blade. Are the two easiest to manage in early levels.

To level up easy either lightning main or water main but i think lightning main is a bit easier. After that it all just depends on the ninjas you get at that point it just depends on the ninjas that work best with what main.

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.

I would always start with fire main. Especially with mirror and 10 chase. 9 tails with fire main and tenten and kiba because of chases is what helped me stay ahead in that regards.

I think starting with lightning main is best and then you can switch to azure at lvl 60. Wind main is only good if you have the right ninjas to pair up with her.

Could you tell me how the hell, should I have 200 scrolls in the second month ? :D
I m an active player, online daily about for 8 hours(ofc I m not always in the game sometimes I open it and wait for an event and so on), but the point is I do all the events everyday, all the daily practice,arena,ranked battle etc. And in 1,5 weeks I got 26 scrolls (BUT from 26 I bought 10 myself and its a new server and because of that we got some free scrolls in the beginning). So I would say my gathering rate is around 10 scrolls in a week at top even though if I m always active and I m doing participating in everything.
Thanks

PS: I m not mocking you, I just want to know because I m a new player and I just dont see a way how to get 200 scrolls in 2 months.