Skyrim is going to have unique landscapes, not randomly generated anymore, and the dungeons SHOULD be vastly different, seeing as there are 8 dungeon designers for Skyrim instead of just one for Oblivion. I think those two things combined should be incentive enough to travel more. However, I can't guarantee there's going to be a huge variety of dungeon styles, not any more than Oblivion, at least.
I'll not let cheap stuff like unimmersive fast travel ruin my first play of Skyrim.
Fast travel is only unimmersive to those who can't suspend disbelief. If I walk all the way from Point-A to Point-B and then fast travel back to Point-A, that just means my character walked back the way he/she came without anything interesting happening. I can't tell you how many times in Morrowind I've done exactly that. It's like having a scene change in a movie. Just because you don't see it happening doesn't mean it didn't happen.
Regardless, saying fast travel would
ruin your first playthrough of Skyrim sounds a tad extreme, especially when it's a completely optional function.