I love how the currents are set up so that we get everything just by progressing through the story. Some people like to unlock flying first then do the remaining side quests, but I always do them as they come. Questing with flying is a sure way to diminish the feeling of adventure. It's a once-only experience and I am glad I did it this way.

PS: The moogle quests are worth doing. If only for the ending.