Here's an idea that seems pretty radical, but I think it would be really cool if instead of a horse, Link rode some kind of flying creature in SS. It would make sense with the gameplay, as it would allow Link to go between Skyloft and Hyrule without warping. I also think that it would fit the game's impressionistic character quite well, as it's a great design opportunity and flying around in the skies above Hyrule could really showcase the beautiful clouds and other such aesthetic denizens of the atmosphere.
I think a winged horse, like Epona, would kind of fit, or if at some point in the story Epona received wings (as a dungeon item or a great fairy's gift or something) would also work, but I think it would be best if it were a different creature altogether. Something large and feathered would be best, IMHO. It would fit the game's style and still feel pretty epic.
Note that this is not a prediction. This is a suggestion of what I would like. There is a gargantuan difference.