Planänderung: Mapbox hat mir über das Community-Programm für EVMap einen kostenlosen, vorerst unlimitierten Account angeboten. Mapbox hat den Vorteil, dass es Vektorkarten verwendet (im Gegensatz zu OSMDroid, der "Standardlösung" für die Einbindung von OSM in Android-Apps) und die Client-Bibliothek vollständig Open Source ist (im Gegensatz zu z.B. TomTom und Google Maps). Außerdem ist die Schnittstelle sehr ähnlich zu Google Maps.
Ich bin dabei, das nun so anzubinden, dass man dannn in der App zwischen Google Maps und Mapbox auswählen kann. In Zukunft könnte es dann eine zweite Version der App geben, die nur Mapbox nutzt und so auch auf Geräten ohne Google-Dienste läuft. Die wäre dann vermutlich auch geeignet für die Aufnahme in F-Droid.