Well, the main thing to remember is that the Palm, Handspring and the newer Sony clones all use different add-on formats, although adapters for some connectors are now becoming available (according to Palm Tipsheets). Pick the one that has the right add-ons that you think you might want.
On the Linux end, I have coldsync working well with a serial cradle. I don't know if USB works as well, as I don't have that. ;-)