Yes!, i think i finally nailed this popular debate and allow me to feel enthused! Let's state this clearly:
I'll be discussing the "Map Fast Travel" where you pop your map in any exterior area, click a location and voilá, you've made taking the bus obsolete. Wait... isn't the bus not invented yet?

You hate fast travel? You couldn't live without it? You want it to be optional? You're repeating "if you don't want it, don't use it"? You know that if it's there it'll make you feel like a fool for not taking advantage? None of the options cater to all audiences? Here's what we'll do:

The Fast Travel Perk
At a certain level after the player creates his character, solves a handful of quests, has traveled and explored by foot some miles and gets a bit of a taste of the game (say level 5-10) the player is presented the choice of one of two opposite Perks:

Fast Traveler: You now get the option to fast travel from your map to any location known/marked by NPCs, and gets "x" minor bonus. Or it could be a tiny penalty, like a brief temporary health weakness after traveling or something else, that could simulate the weirdness of teleportation. You get a big advantage, with a small plus or a small penalty. Or on a completely different mechanic, maybe non-exclusive, you'd have to pay only 1-2% of your gold for fast traveling compared to a bigger amount for foot travelers.

Foot Traveler: You don't get the option to fast travel from your map*, you still have the guilds, hopefully mark/recall and Silt Striders, but as a land wanderer you receive a bigger bonus like your increased awareness makes you reveal a bigger area of the map as you move and more stamina to escape or fight. Or you've been toughened by the roads and have become 50% more resistant to hunger/thirst/sleepiness (but maybe that would apply to hardcoe mode only). Or insert your "x" bonus/es here. Those are some nice alternatives i could think of. So you choose not to get the big bonus of fast travel, but get some significant bonuses instead. And maybe could still use fast travel occasionally but at a high cost.

Considerations
- There are 3 main advantages: it both gives a sense of further 'player customization' by choosing one more Perk, and the sense of 'game customization' by making it adjust to the way you like playing it and for what works for you.
AND most importantly, it would still be available but it would make a difference for gameplay styles and player wishes.
- There is one half-disadvantage: it is not reversible. But it's very flexible!
- *For players who have chosen Foot Traveler, there could be the option to pay 10-15% of your gold to make emergency fast travels. You know, after all, at some point you may wish with your LIFE that you could fast travel, but it has to hurt.
- There is one final challenge: that choosing the perk doesn't fall into choosing it for the rewards, but as it stands, it's pretty much balanced.

Name your Reward!
We need the creativity and experience of the whole forums to find out what the rewards may be. Of course this is to balance both choices and on the same swing personalize the game a bit more to your fast/feet traveling style of gameplay.
Bethesda may take it as it seems that they don't have a strong position over this debate yet, so let's just hope.

So! Without further ado, spill your wittiest suggestions and creativity in the answers! Better if you answer for both!

Thanks for reading! I know it looks like a design document, but that's me. I'll make a poll later with the best couples of answers so stay tuned, and in the end it's all to make it both DEEPER and more immersive!.

what if we though that Oblivion's fast travel was fine and that we shouldn't take a penalty for it? other than that not a bad idea, I know that I wont fast travel for a while though because I would have a lot to explore

You have some interesting ideas, here.

However, I imagine Bethesda realizes that if "map marker" fast travel without any gold cost is not included in Skyrim, it will piss off a majority of the people who purchase the game. I would be extremely shocked if this is not included.

Maybe there will be a % chance for random encounter, and maybe there will also be some morrowind-style teleport/silt striders, etc. incorporated into the game, but the devs are not likely to include any gold cost for clicking on map markers, or withhold the ability to click on map markers until completing a quest, etc., or getting a perk, simply because it would piss off too many people who are not hardcoe Morrowind fans.

I don't really think there should be any penalties for fast travelling, except, maybe, making it take longer in in-game time than travelling by foot / horse / whatever would have. Maybe a gold cost to make the trip go a bit quicker, like Daggerfall's "stay at inns" option? But nothing more than that. I can't imagine it being very easy in the slightest to balance that sort of thing, and it's more likely to be a mess any way you go about it. Choosing to fast travel or go by foot has its own natural benefits and penalties built in depending on a person's play style... personally, I like to choose between the two depending on how I feel at that moment. Exploring the path along the way is a lot of fun, but sometimes I just want / need to get there. Having to pick one or the other and stick with it no matter what would just be a mess...