Es según como se implementa en cada aplicacion. Para rutear se necesita la informacion de la red vial. Hay aplicaciones que tienen solo una descarga para toda la zona, otras lo reparten en distintas funcionalidades y cada usuario tiene la flexibilidad de elegir a su conveniencia. A veces el reparto es por razones puramente comerciales, otras por aspectos tecnicos, o por restricciones de licenciamiento.

Te dejo un par de opciones de navegadores libres que tienen todo offline y estan en fdroid.
Maps (fork libre de otro comerciai) https://f-droid.org/en/packages/com.github.axet.maps/
Osmand https://f-droid.org/en/packages/net.osmand.plus/