Qualquer sistema operativo (que eu saiba) corre java que já tens aplicações bastante interresantes: só para fazer log do percurso tens o Endomondo e se queres ver mapas e seguir tracks (em offline) tens o Trekbuddy mas há outros tb,talvez aquelas imitações de Iphone do chines sejam uma excepção,mas Samsungs,LGs,HTC,Alcatel,Nokia,etc... qualquer um dá.Isso agora é uma questão de gosto pessoal.
Depois há aplicações especificas para cada plataforma: Symbian,Android,Windows Mobile,Apple IOs.Nessas já não posso ajudar pq nao conheço.
A cerca de um ano procurei o telemóvel mais barato com GPS,WI-FI e boa capacidade de bateria.Acabei por adquirir um Samsung Monte por 80€+pontos na minha operadora.Sem ser brilhante (GPS pouco preciso) e ter um sistema operativo proprietário sem aplicações especificas acabei por ficar limitado a aplicações java.Em stand-by e poucas chamadas a bateria ( Li-Ion 1000 mAh) aguenta praticamente uma semana.Mas a fazer de MP3,camara fotográfica e GPS a ver mapas (com o ecran sempre ligado) na melhor das hipoteses aguenta 6 ou 7h.Mas dificilmente recomendaria a outra pessoa que queira usar como GPS pq precisa de alguns "tweaks" para funcionar sem problemas (assim como todos os Samsung com BADA OS) já que a Samsung não é muito ortodoxa a implementar funções.
Mas a maior limitação destes telemóveis é o GPS ser A-GPS (Assisted GPS) e como tal só funcionar dentro do alcance da rede da operadora.Mesmo desligando o A-GPS e correndo só o GPS nativo se estiver fora da cobertura da rede consigo ver no menu do telefone a minha posição em coordenadas mas o software para "trackar" ou ler mapas recusa-se a funcionar,isso é o maior aspeto em ter em conta.Pode ser que seja um problema especifico da sistema operativo da Samsung (BADA OS) mas não tenho outros para experimentar.