Preferably something that supports SyncML, the standard protocol used by mobile phones. Even standard Nokia phones (i.e. non-Symbian) have decent PIM support: a workable address book (that lets you specify multiple e-mails and phone numbers per contact) and good SyncML implementation.

Supporting SyncML would allow interoperability with OS X and Linux (though Linux's OpenSync implementation is a bit flaky). I'm sure there's a SyncML-compliant synchronization solution for Windows too.