> However, their server still needs to know where users are temporarily in order to send a map of the local area.

Serve the maps in very coarse blocks that are downloaded ahead of time (and updates are served as binary diffs) so the smallest region the backend can pinpoint is the current city.

Over a decade ago stand-alone GPS units with single-core, sub-gigahertz CPUs, RAM measured in dozens of megabytes and shitty slow SD cards managed to hold maps for the entire country, so there's no reason devices orders of magnitude faster on all fronts can't do the same. In fact, in the iPhone 3G era I remember buying a GPS app that embedded all of Europe's maps locally and it worked well (in fact, local search is actually faster than online search).