I wonder if there's a game that focuses on that sort of travel experience.
Back when there was Morrowind, which didn't have map markers and whose in-game map had to slowly be uncovered. You get a description and that's it. The game did come with a paper map, which was stuck to my wall for years and frequently consulted.
A modern one would be Kingdom Come: Deliverance 2; when you turn on hardcore mode (which was only added after release, but the game was designed with it in mind), you don't get your position on the map, compass, or map markers; every quest involving a location has the NPCs give you a description (and at least in normal mode, your character making a remark when you've reached a landmark). It's not so much about planning your route though.