The original Fallout games had a vehicle you could use as 'fast travel', I think that approach is a very immersive, while still not terribly annoying solution. Essentially: you want fast travel in a game? Add a fast, but combersome vehicle! makes sense to me
The vehicle was just cargo and faster map movement. You stepped out of an 'encounter area' and onto the larger 2D map view. (like in Wasteland 2) Personally I like travelling the map in 1st or 3rd person view. Especially when you encounter firefights in the distance at night.