Google Maps is great, but unless you have an unlimited data plan, it's going to cost a lot downloading all that data all the time.
Do you know of any (preferably free) good offline map application for Android? Ideally one that can do navigation (preferably with voice) and in my location (Sydney, Australia).
Yah, there is a terrific one, called Maverick Lite.
Off-road GPS navigator with OSM, Google and Bing maps. Support for offline maps & multi-touch. Build-in compass, timer and trip computer. Share your current or planned location. Record and upload tracks to GPSies.com. FourSquare support.
And it's free. the paid version costs about $4
There are quite a few that use openstreetmap data. This is a review of MapDroyd and BigPlanet and the openstreetmap wiki has a comparison of android clients - look in the first column and look for "online + offline".
In the near future Google Maps for Mobile 5.0 will be released, whose new features include offline storage of area you visit frequently.
There is a hack for Google Maps that allows for cached offline maps. It can only do navigation in the normal way while connected to the Internet though.
Brut Google Maps
I like Waze. It is free, works offline (synchs when you're connected to the internet in some way other than 3G).
Its main advantage is feedback from users. It provides live traffic updates from other Waze users.
You can find it here:
You can created offline version of Google Maps with on your PC and use it with RMaps application on Android. Works very well for me.
You can download RMaps from Market: https://market.android.com/details?id=com.robert.maps&hl=en
And here is a guide on creating offline maps: http://xslab.com/2011/03/rmaps-offline-navigation-tool-for-android/
Recently, there is a new option: Sygic. This is one of the most important companies in the development of navigation software for mobiles. TomTom has also announced that will launch an Android application in the next months.
NavFree is free and allows you to download maps for offline navigation.
I use Custom Maps a lot myself, but you need to put a map image on your mobile yourself and match a few points up with Google Maps to make it work off-line. I often grab screenshots off NZ Topo Map for taking bush with me using Custom Maps.
OsmAnd is free popular Offline maps for Android.
The best part is OsmAnd is GPL Open Source.
You can help support this project buy purchasing the OsmAnd+ version. This gives you access to download an unlimited number of maps, and access to Wikipedia sight seeing POIs. This app is well worth over double the price they are asking.
A very good navigator is MapFactor Navigator Free. As the name suggests, it's free (as in "free beer", not "free speech") and it uses Open Street Maps (free as in "free speech and beer"), directly downloadable by the application menu.
As of today it's still in beta, but I tried it and it works well, comparable to if not better than Sygic, which I was using before.
MapFactor Navigator is on Google play.