GPS легко докупается к любому КПК.

Например:
http://www.ultra-online.ru/common/good_ex.php?site_id=2&small=1&id=79637

посоветую не смартфон а коммуникатор (это КПК+телефон)
отличие
смарфон : форм фактор - телефона и нет тачэкрана
коммуникатор : форм фактор - кпк с тач экраном

посоветую qtec как недорогой

qtec S200 (с windows 5) но пока дороговат
qtec S9100 (с windows 5)
qtec S110 (с windows 2003)

у любого коммуникатора есть мини недостаток
разговаривать лучше через блутуз гарнитуру

к любому коммуникатору можно подцепить GPS модуль
как вариант через блутуз

да есть полные аналоги qtec это I-mate например