Well, there are Treos that run the Palm OS so he could retain the functionality, look/feel, etc. that he's been used to. Versamail can do scheduled, manual, and push email via ActiveSync as long as webmail is set up on the Exchange side. Calendar & contacts sync over the air at the touch of a button (menu option) when wireless and/or during a cradled Hot Sync.
The Centro is the least expensive Palm-based SmartPhone. But the keyboard is a little small for my taste (just right for my wife). It's geared towards the consumer end while the Treo-branded units are prosumer/business. Some Treos run Windows Mobile; some run PalmOS. WM units generally have a W in the model number.
Palm OS is aging a bit less gracefully than I'd prefer. Supposedly a major new release will be out later this year. But anything you buy now probaby won't be upgradeable; SmartPhones rarely are (the do usually get a maintenance release or two). Still, it works well enough. Any Centro/Treo can be used to play MP3s, supoprt bluetooth headsets for phone (and stereo BT headsets for music via extra app). The cameras are what you'd expect. There are thousands of apps, both business and entertainment, available. The built-in browser is fine and Opera is available. Google has a couple of apps that run natively on it (Maps, GMail via Java Micro Edition).
Treos and Centros in general have craploads of
accessories, from extra life batteries to dozens of cases, etc. There are also lots of community sites like TreoCentral.com, mytreo.net, etc. where info & forums are available.
BlackBerrys are fine for email but are a little behind in other areas. They have improved a lot, though. Depending on how things are set up you may need a BlackBerry Enterprise Server next to the Exchange box. In the old days you had to tether to sync calendar & contacts but I think that's resolved in newer hardware.
If using it as a business device, avoid the iPhone and probably most of the minor players.
Recommendation: If your client still likes the Palm platform, there's no reason for him to have to learn something totally different. Buy a Centro or PalmOS-based Treo, Hot Sync his existing setup from his PC to the Treo, and be on your merry way.