Подскажите на какой базе работают навигаторы? (android,кпк) На какую базу скачивать карту?

Под навигаторы существует масса програм. Таких как автономные (для них необходимо скачивать карты (как то GisRX CityGuide Navitel) а так же зависимые от интернета (Yandex карты, Google Maps Yandex навигатор и прочие) .

Каждая программа требует свой формат карт (но если карта не закрыта то можно транскодировать из одного формата в другой)

Наиболее известные програмы типа Navitel или Yandex карты кроссплатформены и будут работать и на iOS и на Android (Linux based) и на WindowsCE/Mobile/Phone