I meant travel = difficult more as it represents some kind of commitment towards moving on rather than as OMG you're going to get squashed like a bug. This would mostly be accomplished by not having "shortcuts" like WoW's gryphons and hearthstones or Oblivion's autotravel. Also, the farther you go from known towns, the harder it is to maintain built up reputation and/or wealth. But if you do the game right, the option of adventuring like that is worth it.
I think an interesting option for leveling in a RPG would be to get away from the exponential XP model. Instead, something like Oblivion's various skill levels, but each limited to a smaller linear range, perhaps a master level in a skill would be 5 times greater than a beginner. 0-5, 0 representing no skill in that area, 1 beginner, 2 basic proficiency, 3 well trained, 4 expert, 5 complete mastery. Each level is harder to obtain than the last, so that going from 4-5 represents a pretty decent commitment. Also, skills get rusty, but only to a point, so over time, without practice, a skill will fade at most 2 levels. So if you really spent the time, you could cap each skill in turn to guarantee that everything is at minimum 3s.
Fights or other challenges would then never be a matter of getting one-shotted, but would be more a matter of mustering the correct training or resources ("hmm, this creature is too tough, wonder if I can hire some extra muscle at the inn...")
One of the programming challenges is getting that good mix of random quests in new areas that range from the starters to earn skils and resources, to those epic quest lines that can lead to great rewards if the player wishes to make the effort.