上のようなOrganic Mapsというアプリもありますが
Googleマップより使いづらい上に機能では劣っています。
住所検索や航空写真が使えません。その上市街地では情報量が少ないです。
しかしサイクリングやハイキングにおいてはかなり良いです。
余談ですがGoogleマップ用のXposedモジュールもあります。
Androidスマホは位置情報サービスをオフにしてもユーザーの位置情報を追跡していた | ギズモード・ジャパン
またプライバシーを大切にするならAndroidではなくGrapheneOSやCalyxOSを使うと良いでしょう。