I use the Cingular 8525 Smartphone to compliment my GTD implementation. I have it wirelessly sync with my Outlook 2007 client (exchange). It has a real nice size keyboard so entering new action items is quick and easy. I installed Pocket Informant on it and have my action lists sitting in the tasks sorted by the categories (context). It nice, smooth, and quite functional (at least for my use). You may want to consider.
If you need an unlocked version, you can google HTC TyTn. Same thing as the 8525