The first being Morrowwind's system of Ships and Silt Striders, suplimented by various spells such as Mark and Recall.
The second is Oblivion's "Optional" Fast Travel that allowed you, from day one, to get from any of the major cities instantly by simply touching it on the map. This was then suplimented with the ability to fast travel to any location out in the world, provided you had been there before.
These two systems have created a great divide between players with one side favoring the immersion of true to life travel and the other the convience of instant fast travel.
This is why I suggest a Magic Map Quest.
Those who don't want fast travel, or want the immersion of Ships and Carriages will get what they truly want and that is to use the world to travel. They are happy. They say "Give me a Mark/Recall spell and a boat to Solitude and I'm Happy."
Those who would prefer to have the option to touch a point on the map and just *POOF!* appear there instantly. Well they can use the Ships and Carriages to get to all major(and maybe some minor) towns from day one and then eventually they go on a quest (similar to Nocturnal's Skeleton Key Quest ie: Early on but not too soon) and are rewarded with the Magic Map of the Hero of Kvatch! Legend says he was able to simply touch any point on the map that he had previously been and *POOF!* he appeared there.
In this case, everyone wins. Even the Devs, who would need to put little effort into restoring Morrowinds Fast Travel Hubs in each town and we know the "Magic Map" already works... Well, a little effort, writing a decent Daedric quest to find a 200 year old Magic Map and, of course, adding some Boats and Carriages outside of towns.
As I see it, this could be no different then the Skeleton Key. Some want the challenge, some don't. Both remain immersed in their respective worlds.
See? Everybody wins.