No fast travel is usually a constraint I set to myself, no mods required. The HUD is a different thing, though, because a lot of times the game relies on the fact that it can pinpoint you to the precise location you need to visit, and doesn’t provide alternative directions. But yes, without it you really view the game world with different eyes!
It’s really one of those games where the stars aligned, so to speak. It has this meticulously crafted world that feels like a real place, with all these distinct and characteristic locations to get lost in, a rather good (if, somewhat artificially protracted) main story and great game systems.
Of course, it also had the advantage that the internet was still in its infancy, and you would not be tempted so much to look at guides, hints or spoilers and could experience the game in a much more intimate fashion.