To expand on my idea of just giving the HMs like fly even more uses, you could have a spot on the map with a script on it that checks if you have fly, if you do it says you can fly up to somewhere, if you select yes it could go to a map wheere you fly up in the sky around somewhere, and items/trainers/fishing spots/grass with rare pokemon in it etc could be found. If you descend enough you are taken back to where you were on the map, back on foot. When flying it could automatically find the first pokemon on your party with fly and use that as the mount. With 3d environments and the ability to go up/down you could make some pretty cool new maps, Bonus Content.