Maybe it's because my main class was an Archer (They get the movement song), but I never really needed to "grind" for the seals, and in fact felt it wiser to just participate in any Fates you happen by while you continue to do quests and the main storyline. Maps don't really get so large that a mount is absolutely necessary (The only one I've found is the southernmost section of South Thanland), so it really doesn't put a hamper on the speed at which you level.