Mac compatibility of Smart Phones other than iPhones?

So, my old cell phone is toast. I would like to get an iPhone and synchronize it with my MacBook Pro - however, my mobile phone company does not support iPhone.

Here is a list of what they do support. What are your experiences with any of these and their compatibility with Mac? I have heard tales of people going through hoops and not getting much satisfaction. I could change providers, I guess, but I’ve no idea of how binding our current contract for bundling is… (I need to read through a lot of this information; it’s just whenever I start, I feel a sudden urgent need to do something that isn’t irritating.)

Please, what are your experiences?

Check out Missing Sync. I used it to sync my Windows Mobile phone to my Mac and it worked pretty well. They also have versions for Palm and Blackberry so you should be covered. I think it was about $40.