Needless to say, Kingdom Come ended up with fast travel, but it's implemented quite tastefully - you have to discover fast travel points, as is common in all RPGs these days, and travelling (especially at night or through risky areas) always represents a risk of being ambushed.

It's definitely a game that rewards exploration, not just with finding random chests or gathering dumb resources for crafting etc, but exactly as the post hopes - because it's beautiful and atmospheric. I found myself spending a lot of time hunting in the game, not because I needed to, but just because it was nice to be out in nature. The game is 5 years old but (perhaps with the exception of RDR2) I don't think a single RPG since has got so much right in one game.