1) Services you have to do quests for to activate. Clear the route between stable A and stable B from bandits, and you can use that service. So even if you know the basic area and don't have to discover the main towns (makes no sense to me not knowing *anything*), you still don't get the option to bypass into the other towns that should be unreachable for certain parts of the game (non scaled opposition).
2) Variation. Make newly opened services be available only at certain times or days. Maybe it is already in use. Quest to hire more people for longer hours and better options. Maybe the service is over run, forcing you to do it all over again but maybe with a twist to the quest. There is a ton of creativity that can be utilized on this alone.
3) Boats are generally not in service until you've cleared the northern cities land routes (wasn't there only three main coastal towns?). Let it be a country in massive logistic (?) problems that you can choose to help solve. Maybe these quests are done automatically by other adventurers anyway, further down the line? Who knows.
4) When you get a horse, you may have to slow (not fast) travel if you're loaded with items. Slow is having to walk (not run) with your horse, and you shouldn't be able to bypass over encumbrance effects like today. Means having to camp, and camping can be interrupted. Only works with a good "sleep and eat to restore fatigue fully" system implemented.
5) Mark should be a rather heavy item, a mobile portal of sorts. I even want it restricted to cell (if game still have those). Recall could be a rather high level spell.
6) Intervention spells should be restricted to exist only as scrolls. Maybe even unique ones. I consider these "get out of jail free cards", and with such limited supplies it's not something you will rely too much on, at least not as a convenience thing. If available in great numbers, then maybe allow for "stuck in dungeon" situations to compensate, something that is lacking in OB (and I don't like getting stuck for any reason really).
7) Mages guild travel should be a high level guild perk. Maybe you help invent the stuff? Maybe you're not allowed to use them if you're also in a competitive faction (not fighter or thieves guild, but another type of mages guild, maybe you even help form it?) that allows its own version of guild travels.
8) Maybe the fighters guild offers escorted fast travel to any location you've been at? Kinda one way, but still...
9) Maybe fast travel as we have it today becomes a possibility once the main quest is done? Numerous ways to make that a good part of the storyline. Maybe it's a spinoff where you only get to choose one of three branches of quests. For us that don't like fast travel, we could choose to do another quest that gives other attractive alternatives - like a certain set of boots But have it as a true consequence to a relevant quest, rather than "I pick fast travel".
If fast travel like we know it today is available from the start, there would be no point in having all those others. If a dice based game had fast travel, and the GM wanted us to discover a certain location because he planned it, he would disallow fast travel for whatever cheesy reason he could. So I think keeping it varied and dynamic, it feels more like a living world than Skyrims predecessors.