With the ability to fly, you can now do a lot of things. You also have the Seek Fortune spell, which reveals the locations of hidden chests on the world map. One of your first stops is the Genie's Steps, which are the plateaus surrounding the Temple of Trials. You're looking for the Dinoceros, which seem to only be in battles when you find it walking around (they don't seem to be mixed in with the other enemies). You want to tame one because they are one of the best attackers in the game.
If you didn't do it before, go to the one island north of Ding Dong Dell and recruit a Toko. These give you a lot of experience when killed, so they're useful for leveling up some. If you do manage to capture one, though, it takes a long time to level. This island also has Mites, Thumbelemurs and Seed Sprites if you need any more.
