Ich würde auch zu einem series 60 Nokia wie den von Macflieger erwähnten raten. Allerdings sind alle mir bekannten, auch das schicke 3230, daß ich seit kurzem mein eigen nenne, vgl. schwer und bis auf 6880/6881 (teuer) auch nicht die schnellsten. Dafür gibt's dafür Software satt, den besten Routenplaner für Handies (Navicore), und das aller, allerwichtigste: FRODO, einen C=64-Emulator.
Mein 3650 syncte gut, das 3230 konnte ich noch nicht ausprobieren, Bluetooth-Dongle ist hinüber (kommt davon, wenn man ihn in eine Tasche packt und die dann in die Ecke pfeffert...
).
Ansonsten kann ich noch ein SonyEricsson T610 empfehlen, daß hatte ich mal. Derzeit sehr beliebt ist ja das K750i, steht auch auf der Liste, aber ob es gut klappt, weiß ich nicht.
Zu Palm kann ich auch nichts aktuelles mehr sagen, früher ging es ganz gut, aber da iSync sich mit jedem Update zu verändern scheint...
Überhaupt kann man generell sagen, daß (BT-)Syncing via iSync so eine Sache ist und selbst wenn ich hier schreibe, es funktioniert, heißt das nicht, daß alles 100% und immer gesynct wird.
Deßhalb würde auch ich raten:
Wenn Du einen iPod hast oder schon immer einen wolltest, nimm den. Das geht wirklich stressfrei. Z.Z. sind ja minis im Ausverkauf...