Exploration in the traditional sort would work best in low to mid levels. Most sort of transportation magics, though, are for instantaneous travel to and from somewhere; this ironically leaves little for exploring things in between. In high fantasy, overland flight, flying carpets, and airships might replace regular sailing ships for exploration. So you could just shift the swashbuckling focus from the sea to the air.
Divination magics would probably be very useful in understanding and exploring the world around you, especially find the path, but such spells typically serve to only answer preexisting questions or give information in cryptic ways. Lower-level divination spells cast at lower levels have only a certain % chance of bringing back successful information. If a DM can learn to take advantage of when they fail, he/she can make the party go on wild goose chases or confound them more. It might help to make the exploration open-ended so as to require the characters to actually go out into the world to find something or to map it out. As an alternative, you could simply treat wilderness adventures as dungeons but with different dressings. Another thing about magic is that many spells require the use of expensive material components made from natural resources, especially minerals. It would make sense then that, if such costly natural resources were widely used by spellcasters, that eventually resources in one place would dry up. This would create demand for explorers to map out new territories to acquire such wealth.
Translation spells like comprehend languages and tongues make communication relatively easy between foreign cultures, and this could actually facilitate instant contact between the party and the natives of the places they live in, although this would not affect any culture shock they might have. It would probably greatly reduce the need for foreign translators. Different areas of the world might have different magical conditions- dead or wild magic for example. Different systems of magic for different cultures might interact with each others in strange ways. For example, how would a defiler from the world of Athas work in a lush, green world that does not require defiling?
The use of spells also might allow explorers to solve ancient mysteries and gain details of past civilizations like modern technology does today. Using divination magics, speak with dead, etc. might allow an investigator to determine if the long-dead baron really did murder his children. What killed the ice man under the glacier? Fantasy also allows for interaction of widely diverse people (and alien beings) that could require role-playing no matter what the magic level. Perhaps the PCs are the fantasy equivalents of anthropologists trying in depth map out the lives of foreign races that can't simply be answered by divination spells and their brief answers.
Another option might be to change the areas of exploration. In a high fantasy world, the frontiers may come in different forms. The planes might serve as neat areas of exploration, considering how they are often incredibly difficult to survive in and sometimes alien as well. In such a setting, a planar town, such as Sigil, might be described as more of a "last chance" town on the fringe of civilization and serving as a base for the PCs as well as a place to link different reality frontiers together for the PCs to explore.
