Yo he tenido varios móviles con A-GPS como el nokia 5800 o el n97 mini y he estado con el Sygic sin problema ;) (y sin ninguna tarifa de datos, claro)
Ahora con el Skate Estoy con el Sygic para cuando me voy al extranjero ya que no utiliza datos, y para ir por aquí viajes cortos el Navigation ya que el consumo de datos es mínimo.
Para mi la mejor opción es Sygic o IGO. Ninguno necesita conexión a internet y funcionan perfectamente ;)
Un saludo