By using an offline GPS app, you no longer have the need to coordinate with a centralized server. In exchange, you will lose traffic data. There may be some app that gives traffic with a level of privacy loss that meets your needs, but generally the data collection compromises your privacy, and the data is valuable... Anyway, OSMAnd is a popular F-Droid app I remember hearing mentioned.

But, if you don't need traffic, then you could theoretically navigate with all your radios off, so you wouldn't be talking to towers. The experience will probably be quite slow, even with all the navigation constellations available now. The increasing incorporation of L2 and L5 GPS may improve that, but generally you're asking for niche performance, so I wouldn't hold my breath.

I think people typically leave data on and prefer to just buy prepaid phone plans anonymously, paired with some combination of VPN usage and not using the phone for anything with a login, hoping to break the chain of tracking between the phone and the user's identity. It's probably enough to stay out of geofence warrants, at least.