I only have experience getting a second class from 1-17, but it was really easy, just follow your hunters log, doing FATES anytime you see them. Honestly, questing on a second, third, fourth, etc. class actually SLOWS DOWN leveling. You don't get the bonus XP for completing them like you do with kills, fates, hunterslog. Of course I"m not saying NOT to do them, just saying if you're ONLY concern is leveling up, you'd want to stricktly go for kills.

I actually like this system. I remember the "good old days" of FFXI and after level ~12, it was just amazingly hard to level up. Heck, I never got a character to even level 75 in that game (although I had 3 or 4 past lvl 30)