Palm M500's (515, 505) are available used cheaply and work fine with Macs, and are very small, light and reliable.
You might consider a Treo smartphone, since it will give you all the phone features plus the PDA features. Bulkier than the M500 tho.
Tungsten E looks nice, but reliability is a concern.
Forget PocketPC or whatever they call it these days. It is a baited hook from the dark side.