I used Google Sync when I had a Blackberry, and it was a lifesaver for me. Then again, I don't mind the "over-polluted" auto-saved contacts list that I get with GMail. It turns out to work pretty well in Android.

Also, it looks like the options for the iPhone are a little sparse. I could have sworn that on the Blackberry version, you could choose to narrow the contacts that get synced to your phone, like only the items in "My Contacts" and not everything in "Suggested contacts."