Of course the above demonstration has two fates and a dungeon being run in half an hour when the Original poster is pointing out that it takes them forever to get into dungeons. And no, they aren't being hyperbolic. It takes me damn near forever to get into a dungeon as well ((I make do soloing FATES though. I suspect her equipment may be to blame on that account.))
We can't just take the basic point ((leveling takes forever)) and ignore the additional factors ((Can't get into dungeons with anything resembling regularity, can't find people running FATEs, stats too low to do them Solo)).
Related, the FF XI fate is a godsend. It pops regularly, the Crabs don't agro unless you attack them, and they're all level 27ish. Though running that several times is probably boring.