> Google maps works okay on slow connections if you download the tiles for the city you're in beforehand

At that point, why would you use Google Maps at all? Osmand will do the same thing, and requires no connection.