Ja używam PathAway, z zeskanowanymi mapami papierowymi (można też kupić cyfrowe wersje niektórych map, do skalibrowania).
Można też kombinować z softem Garmina (Mobile XT) i mapami z mapcenter/mapcenter2, jednak w przypadku palmtopa z tego co słyszałem średnio się to sprawdza (Mobile XT jest przeznaczony przede wszystkim do nawigacji samochodowej)
Odnośnie obudów, polecam OtterBox'a, naprawdę solidna rzecz.
Ewentualnie rozejrzyj się za odbiornikiem turystycznym - tu już zależy wszystko od budżetu i stopnia wykorzystania urządzenia. Jeśli dużo jeździsz rowerem turystyczny będzie wygodniejszy. A cena przyzwoitego odbiornika (np. Garmin Vista HCx) będzie niewiele wyższa niż cena porządnej obudowy + uchwytu na rower.
Minusem "ręczniaka" są mapy (i tak lepiej od jakiejkolwiek nawigacji drogowej, ale zwykle sporo słabiej od map papierowych*)
Plusem jest to, że jak się zaprzesz, to mapy interesującego terenu możesz zrobić samemu.
Obecnie na rowerze używam Garmina Colorado, a mapę interesujących mnie terenów właśnie opracowuję :"P
* - mapy turystyczne które są do znalezienia na mapcenter/mapcenter2 są często sporo uproszczone w stosunku do ich papierowych odpowiedników, co oznacza że np. części dróżek po prostu nie ma... Nie jest to problem jeśli jeździsz od-do, jednak jeśli chcesz się "pokręcić" po lesie, to zaczyna to trochę przeszkadzać.