Интегрированный вариант:
HTC Wildfire, платформа Android, цена от 10.500.
Плюсы: GPS встроен, экран больше обычного, всё нужное уже настроено, заточен под Сеть, версия "Пробок" под него есть.
Минусы: разрешение стандартно-маленькое (240х320), телефон встроен, клавиатура экранная.
Вариант: HTC Touch2, отличия - экран меньше на пол-дюйма, ОС WM 6.5.
Вариант: если не пугает возможная потеря годичной гарантии - то HTC Touch HD облдадает ещё бОльшим экраном с разрешением 480х800 при сравнимой цене у "серых" поставщиков.
Вариант: HTC HD2 у них же обойдётся в 13.000 - но это уже полностью современная машинка.
Дифференцированный вариант:
Любой нетбук с Bluetooth. Потребуется внешнее устройство GPS (не встроено ни в одной младшей модели) и связь с Сетью (GPRS не встроен ни в одной, WiMAX в трёх) - то есть может понадобиться GPRS/3G/4G-модем (оба устройства могут быть и USB и Bluetooth). Первое стоит 1.500 - 2.000, второе от 300 рублей.
Для абонентов МТС и Мегафона траффик Яндекс-карт бесплатен.
Я бы выбрал второй вариант, если есть возможность всё это возить в автомобиле и носить в небольшой сумочке - и первый, если критична компактность. Первый предпочтительнее именно из-за клавиатуры, ибо набирать на экранной удобно пару абзацев - но не более того (психологически комфорт/скорость ввода падает).