Google maps é ótimo, mas a menos que você tenha um plano de dados ilimitado, vai custar muito o download de todos os dados o tempo todo.
Você sabe de qualquer (preferencialmente livre) Bom aplicativo off-line do mapa para Android? Idealmente um que pode fazer navegação (de preferência com voz) e na minha localização (Sydney, Austrália).