Check out Palms for out-of-the-box sync-ability with Macs. You can sync Sonys and Windows handhelds, but you need third-party software to do it.
I agree with "question fear" that you should go to a store with a good selection of PDAs and play with them. The experience of using a PDA depends so much on the physical interface, input methods, and display quality that you don't get much meaningful information about PDAs from the specifications sheet. Try 'em and choose the one you like the best.
That said, the Zire 21 is crazy cheap, the Tungsten E is a good deal with good functionality, and the Tungsten T3 is expensive but pretty cool.
Good luck!
Crikey
PS: The latest reviews claim Pocket Mac is really, really cool. I have a Palm, so I wouldn't know.