Travel distance could be measured with a progress bar. As it moves along you could get little notifications, and options on how to respond. Examples:
[Enemy type] nearby: Engage (exits Fast Travel), Sneak By, Go Around
[Ingredient type] nearby: Explore (exits Fast Travel), Ignore
[Dungeon type] nearby: Explore, Ignore
[NPC name / profession] nearby: Greet (exits Fast Travel), Ignore, Sneak Up (exits Fast Travel)
[Village/Farm/Estate name] nearby: Explore, Ignore
Interesting landmark: Explore, Ignore
Blizzard approaching: Seek Shelter (exits fast travel), Continue (50% weakness to disease for two days)
NOTES:
- You have to watch a loading screen when you Fast Travel anyway! Why not make it a little more fun?
- Using Morrowind style travel such as a ship, or wagon would bypass the mini-game.
- A travel system like this would enable Skyrim to be hundreds of miles across! Travel between cities could be measured in days and weeks! The thousands of square miles of wilderness would have to be randomly generated of course.