That's a really interesting question! The two cities with which I am most familiar are San Francisco and London, and (though I'd never thought about it before) my navigational concepts of them are
very different.
Getting around San Francisco is, uh, grid-like: I think in terms of "corner of X and Y", and then the relationship between myself and my destination on a coordinate plane. Getting there becomes a series of maneuvers - some of them indirect, for route-efficiency reasons (like, this street has timed lights, or this one permits left turns) - which carry with them very few (street-level, at least) visual images of the route.
London is all about pathways, a choice between more and less direct connections between my location and where I'm going. Just about every landmark and decision-point triggers a visual memory of that specific location and choice.
In San Francisco I can point fairly confidently towards a given destination, drive that direction, and find it by "feel" - eg, by intersecting one of the two cross streets on the coordinate plane. In London, I couldn't do that on a more granular than borough / neighborhood level - like, I'd know how to get to, say, Camberwell from a given location, but not in precisely which cardinal direction it lies, and once I get there I'd need to rely on landmark-based directions (or nowadays, GPS).
Navigation in London is more complex, I suppose (San Francisco has its quirks!), but the conceptual framework it requires leaves me with a more detailed and enjoyable sense of the city itself.
That's one person's experience. I'd be curious to know the extent to which it generalizes.