If a substantial amount of action takes place in the sky, I think we'll be able to fly to a certain extent, but not in the usual aspect. I see a few options.
1) Link has to ride through certain areas on things like deku leaves.
2) Link catches a ride from Tingle. Okay, I'm being silly, but he could use a balloon or other kind of "sky boat."
3) Link does have a way to fly himself (such as by using special armor) but it's limited, such as how Medli could fly but only for short times. The length of time he's airborne may be able to be increased slightly, like how Link could stay in Death Mountain or underwater longer in OoT when he had more health.
4) Cuccos are the main method of transportation. (Okay, silliness again, but then again, City in the Sky...)
And other things that have already been mentioned. I personally wouldn't mind the Pegasus equivalent of Epona, but it depends on how easy it makes it to get around. There needs to be a balance of rewarding you for getting her but not making it too easy to skip out on other aspects of the game.