Também uso Windows Phone.
Aconselho-te a sacar, por exemplo, o Gmaps+ e a fazer o download dos mapas de Portugal e Espanha, salvo erro, de forma gratuita.
Também dá para sacar os do here maps, por exemplo.
Depois fazes o download do GPX Viewer e podes colocar um track no telemóvel (no formato gpx) para o seguir. O programa depois usa os mapas que sacas-te (offline, sem gastar net).
Também dá para criando um track novo à medida que se vai pedalando mas para isso uso outro programa.