My ideal travel system would begin with the removal of straightforward Fast Travel. Especially early on in the game. Then Mounts, Magic, Boats, Carriages, all the classic Morrowind options return. You can still travel quickly from town to town, perhaps even use the service to visit an area you've never been, such as a town along the route, so from the start you get all the advantages of a automatic fast travel and none of it's shortcomings. People can still only go to a few select places they have been or along a travel route.
Now as I see it, this is the kicker. Instead of abolishing the fast travel option as it exists in Oblivion. Turn it into a treasure... Just like the Skeleton Key. In Oblivion you could quest for this magic key that would open any lock and you never again had to play the mini game. Some would say it made it too easy but they needn't quest for it. Others would seek out that key as soon as they could, happy they had found such an amazing artifact.
So I propose a Magic Map hidden at the end of a Deadric Quest. One that you need simply touch the location you wish to travel to and in a swirl of magic, away you go. Everybody wins and nobody has to sacrifice immersion.
good point, that would be pretty awesome. i would like to see some form of fast travel that you have to WORK FOR.
it should be like a teleport skill, you get a magic map from the mages guild, and with every mages guild you have a quest chain, when that quest chain is finished the guild leader marks the map with a rune, that rune allows you to instantly travel to that location.
and other quest chains could provide more markers.
its like learning the travel songs in ocarina of time. only there are more songs. XD
[edit] there should be a limit as to how many times you can use this ability in a day.