Most GM's I've played (myself included) with will allow you to have a mount that's capable of flight eventually. Once the game is going if you find and tame some wild creatures or gain a flying beast cohort through trade then you're golden.
The mount is supposed to function like a druid animal companion and druids are quite capable of swapping their companions with a day or so of work so there isn't much reason not to do the same with a cavalier. Limited starting list sure but a horse/pony/whatever is pretty solid to start off with.
GM discretion of course! Dragons, Griffons and Pegasi aren't animals and are also not of animal intelligence so it wouldn't make sense for them to operate in the mount/animal companion system. Iconic mounts certainly but they fall under Leadership and would be Cohorts rather then class ability mounts. Hippogriffs aren't animals and lack the animal companion rules, though I think there might be something on the website for rangers that might work.
Rocs, Dire Bats and similar animals are what you'd want to be looking for. Something with that's got stats for an animal companion. It'd be up to you to actually find and train them though.
Now as for PFS...well that's for them to make things easier for them and not much else.