Factor syncing into your decision
This is a direction I've spent a lot of time thinking about and I've experimented with two devices - the Hiptop Sidekick and the Blackberry. Neither got the job done for me because of the limitations each had syncing to my desktop data. The Treo 600 has become so popular because of its Palm OS architecture but is too expensive and too small for me (it also has an unacceptable low-res screen which will be corrected in the next version due later this year).
The Blackberry almost got the job done but offers no support for categories. And, to take maximum advantage of this device, you must have access to a suitably configured Exchange server (you can not, for example, open attached Office files unless your mail server is running the Blackberry server software as well).
Nokia's flip-open PDA-style device looks nice but also suffers from a low-res screen and I haven't been able to determine whether it supports categories for tasks.
Then there are the Windows Smartphone devices which are also on the expensive side but offer the native sync to Office files and Outlook to consider.
At this point, the best advice I can offer is to take your time, do a lot of research, talk to people who already use each device, and try to arrange a trial before you lock yourself into a contract.