Hmm, been out of the country for a little while now and I'm not sure what the latest is; but I can tell of the few I've used in the past.
a) To begin with, I think the Blackberry is way over-rated. I picked one up a while back and played with it a bit, but returned it due to lack of a cheap upgrade path. With Palm & Windows Mobile devices, there are a ton of apps you can find to extend you phone, not so with the BB and unless you work for a company running Blackberry Enterprise, you won't be enjoying the supposed "excellent" email functionality these are so toughted for. The phone came with some software to install on your PC, but it must stay running resident and forwards emails for you to your phone (I don't like anything opening holes on my PC, esp. a mailer program).
b) While you like Palm, I personally prefer Windows Mobile and haven't gone back to the former OS since I switched. I ended up buying a WM phone by Audiovox. Excellent phone and I was able to unlock it myself using software freely available on the Internet, I could even continue to use it here in Japan but they practically give away phones here so I saw no need (I did test the SIM card though and it worked). Why I loved that phone even more was the Bluetooth (for my GPS & headset) and being able to keep things sync'd w/ work and home using Outlook. Unfortunately TomTom doesn't have any maps for my current area, otherwise I'd continue using this phone.
c) The latest Trio I've seen has slimmed down quite a bit and looks really nice. Not sure about functionality, but of my friends that use the Treo, they all like it and had not complaints.
A final note, almost all Nokias that I know of can be unlocked using freely available programs from most cellphone hacking websites (not pirated software, mind you, but software people wrote to keep people from having to pay to have it done). The Sidekick look spretty cool, but where I lived previously there was no T-Mobile service and Cingular didn't carry that line of phone. Whatever you get, good luck and I hope it works out for you (just make sure it has Bluetooth for your headset
).