I've used GPS navigation extensively on my phone with no internet service; I drove clear across Canada with my simcard pulled, it works fine.

If I had to guess, these conflations of cell service with GPS are a product of misleading UX created by Google. OSMAnd makes the nature of GPS clear, displaying a count of satellites it's managed to hear. Enough satellites to get a location good enough for car navigation almost always takes less than a minute.