For PalmOS devices, if you have the scratch, I'd recommend either the Palm Tungsten W or T and the Sony PEG-NX60 or -NX70V. The Palms should run $450-550. The Sony NX60 is in the same price range. The NX70 is around $600.
All run PalmOS 5 and have very nice color screens. If you want to connect to you wireless access points, I'd recommend the Sony devices; they have a compact flash slot that can accommodate the Sony WiFi card. The Tungstens are Bluetooth enabled, which probably won't help you with connecting to your work's network.
Both Sony devices have the compact flash slot, as well as the Sony memory stick slot. The Tungstens have only the SD slot. Also, both of the Sony PDAs have keyboards, while only the Tungsten W has a keyboard. The W is also a GMS/GPRS phone, so you'd have to worry about service with that.
Both Tungstens are smaller than the Sonys, but that's due to Sonys clamshell design that's used to not only hide or expose the keyboard, but allow you to reconfigure the device in different ways. The primary difference between the NX60 and NX70 is that the 70 comes with a teensy-weensy digital camera. So, basically you need to decide if that little camera is worth the $100 price difference between the two.
For a lower price tier, I'd recommend the Handspring Treo 90, which can be found for less that $300. Color screen, but not as sharp as the above devices, and with only a fraction of the color depth as well. For most users, its onboard 16MB memory is enough, but it does have a SD card slot. It has a keyboard, but unlike the Sonys, the Treo dispenses with the Graffiti input area, so all alphanumeric input is done via the keyboard. Good if you've never spent the time getting proficient with Grafitti. Maybe not so good if you have.
Similar to the Tungstens, the Treo has a line with built-in cellphones. The only one I'm really familiar with is the 300, which operates off of the Sprint PCS network. The Treo 180 and 270 use the GSM network, but I'm not too familiar with them. Like the 90, the 300 has a color screen, but does not have an expansion slot. Also, both devices run PalmOS 4.1, so they're not using Palm's latest and greatest. The 300 is quite a bit bulkier than the 90. For a PDA, the 300 is fairly average-sized. For a cellphone, it's friggin' huge.
Um, anything else?
Cthulhu