Have people tried finding their way around with the minimap completely disabled? For this game, I tended to turn it on/off (primarily for driving during time-sensitive missions), but I mostly played with it off. Just like in real life, getting lost and then getting un-lost is how we learn our way around.
I used to do the same thing in Assassin's Creed games (1-3). Each of those cities had really, really well-done layouts. Lots of little places to hide, escape to, regain ammo and stuff, etc. I think the key is that if you want to learn an environment, it's not fast. And it's not easy. That's realism.
For gaming purposes, I can totally support the argument that we need to move away from floating markers and highlighted paths. My idea for that is that those elements could be in the game, but off by default. Hit a key, and the path appears momentarily, then fades out. Ideally, I'd really like to see a system that just sort of gives you directions, as many describe. I loved making my way from Seyda Need to Balmora in Morrowind the first time, just following the directions you get in the tavern at the beginning.