Lo primero que tienes que hacer es actualizar todo en el Market. Luego, instalarte un GESTOR de Arvhivos. Yo llevo el OI Explorer que es el recomendado por CyanogenMod (una de las mejores empresas de Software para Móviles Android).
Ahora...¿Que GPS quieres instalar? Esa es la cuestión. Yo como tengo tarifa de datos uso el propio de Google (Navigation) que sigue siendo mejor que el resto.
Y es que este depende tanto de la RED de datos como del GPS. Me explico....
Vas en un tunel con soporte de RED y el GPS te sigue informando... pero el GPS no. Porque no llega la señal. Esa es la realidad. Si usas un GPS que lleva datos internos y cuando estes bajo techo... y no pillas un satélite, de nada te sirve.....
... sin embargo el NAVIGATION propio de Android... SI...