I've done 3 classes to 50 now: Warrior, Paladin, White Mage. Working on Black Mage next - currently at 20.

First class I did questing largely, with some dungeons/FATE. PLD got more dungeon heavy with some side quests I'd skipped as well. WHM just a few side quests, largely dungeons, and hunting log/FATE thrown in while in dungeon queue or can't play long.

You'll notice how heavily dungeons factor in. It's because I enjoy them, more than because trying to speed level. FATEs should level you faster if you set it up right.

From my perspective, more side quests would be OK but not necessary. As already mentioned, Battlecraft Leves are really supposed to fill this role. But they're too low on reward currently, so just use them for crafting/gathering or ignore altogether.