My partner has similar struggles and after several years together, I think it boils down to how we orient maps. They use Google Maps' default "map turns around you" mode while I always orient my maps with the North pointing up.
Spatial navigation boils down to learning to position and orient yourself relative to your surroundings. I feel like Google Maps' approach of having the map rotate around you is deeply counter-productive: it puts you at the center of the world instead of emphasizing your movement in the fixed world. It can also mislead you because the phone's virtual compass might be completely wrong and pointing you to the wrong direction.
I have had a small compass on my keychain for more than a decade. When I get off the subway or start a trip, my first task is to determine where the North is. If I don't know it already, I'll check my compass. When I plot a course from the subway station to my final destination, I'll use either a paper map or an app (maps.me, or gmaps) in fixed orientation mode, and determine:
- what direction the A->B vector is (East-Southeast for example), so that I can check it regularly with my compass while walking and detect when I veer off course and need to re-check the map
- landmarks (shops, monuments, boulevards) I should pass by during my trip. If I don't see them, I re-check my position
- turn-by-turn directions (third street on the right, then a left at the roundabout...), with regular direction checkpoint (I should be facing South on this street)
Written in long form, this looks like an arduous project, but I usually perform this in a few seconds, before my partner has finished doing the figure-eight compass calibration dance on their phone. Before I had a smartphone, I used to position myself only with street names and landmarks on a paper map, but I do rely a lot on the GPS position now. I just never trust it for orientation, because my whole system relies on me keeping track of it.