Yo te recomiendo cualquiera con Google Maps, ya sea Android o iOS y que tenga brujula, es decir, casi cualquiera un poco actual. A mi me han salvado la vida mil veces y la navegacion es superclara, tanto graficamente como con indicaciones.
Por otro lado, vas a necesitar si o si tarifa de datos, mas que nada por que de no usarla vas a tardar bastante en coger señal de GPS y si tu intención es guiarte a pie, no creo que te haga mucha gracia esperar 5 minutos cada vez hasta que coja señal.