I know it's not exactly your point, but Etar is pretty nice, and apparently is cross-platform (Android & iOS - which I didn't know), and exists on F-Droid (https://f-droid.org/en/packages/ws.xsoh.etar/), Google Play (it seems somehow wrong to link to the Google Play Store given the context, but it's easy to find there anyway), and Apple's App Store (https://itunes.apple.com/us/app/etar/id1217625781?mt=8). I think OsmAnd(~) [https://f-droid.org/en/packages/net.osmand.plus/] is probably a better choice than Maps.Me.

Given that alternatives to Google products are largely services rather than software run locally on one's own machine, you're probably right about the partial orthogonality of FOSS here since it can be hard to verify that the remote server is in fact running the software it claims it is, and from a privacy-standpoint it may be somewhat irrelevant (I recall even the FSF said something of the sort).