I did agronomy work out in Kansas for a while, which is basically a big grid of very similar crop circles. Thinking on it, there were lots of places I passed by often on the roads, but would never remember, but wherever I stopped and entered a field on foot and discovered all the little differences in terrain that made each quarter unique, I was much more able to have a better mental map of where I was, even if I was only there a few times in a year.

Could it be that you learned the chaotic city better because you were more likely to go around on foot and experience little things, rather than just driving to a box store?

I think this is more about the map. It is easier to remember that you have been at the crossing where that triangle street hits the half-circle road than to remember your position in an isomorphic grid, just like it is easier to know you stood next to that tree in a park (a point of interest) than to remember your exsct position in a lawn where every spot looks more or less the same as the other.