I have a Treo 700p from Sprint. I have a friend who has a 650 and really likes it and syncs it with his G4 Powerbook using Palm's desktop software.
My 700p is cool, but it has some well known and very serious bugs. The main one that bothers me and most people, is that the bluetooth doesn't really function at all. If you want to use a wireless headset with your 700p, oops - sorry - you can't! Palm have been working on a fix for this for a while. Don't know when it might see the light of day. So I don't recommend the 700p, but the older 650 and 680 phones seem fine. The 680 had some battery issues, but those seem to have been addressed.
I went with the 700p because I wanted Sprint's service ($15 a month for unlimited broadband speed internet), and the 700p was their only Palm OS phone. Cingular's internet service is much more expensive ($40 a month I think, and the Palm 650 and 680 won't run on fast 3G internet). But if you only want to use the Treo as a PDA without internet, Cingular would be fine.
There is a software developer called markspace that make a program called missing sync that will sync Palm products to Mac's address book, iCal, etc. I bought it, but found it to be a bit buggy too. There are problems with syncing email addresses in your address book. I've ended up using Palm's own syncing software, and will probably try to get a refund.
One thing to keep in mind about the Treos - if you're used to a typically small cell phone, you may have a hard time adjusting to the relatively large size of a Treo. I've also had a hard time adjusting to carrying such an expensive gadget with me everywhere. Check out treonauts.com and palminfocenter.com for more info and some good forums.