Three months in, the iPhone is great, but I don't deny that there isn't appeal in an Android phone. Though young and unpolished, Google's mobile OS has, unsurprisingly, tight integration with Google services. Much like my own brain, tightly integrated with Google's mail, calendar, reader, maps, photos, and, oh yeah, search. Synchronization between Google services and Blackberries or iPhones had been weak in the past, but some official and unofficial solutions have emerged.
Gmail access on any smartphone has been easy and supported ever since they implemented IMAP. Their help provides setup information for major devices.
Today Google announced that Google Sync for Blackberry can now synchronize your Gmail contacts, in addition to Google Calendar events and alerts. Any changes made on the Blackberry will sync back to Gmail/Calendar. This also makes moving to a new device easy.
For iPhone users, its slightly harder because Google can't have it's own app running in the background synchronizing changes. NuevaSync is a solution that I've been running without issue for a couple months now. The iPhone supports Microsoft Exchange for mail, calendar, and contacts. NuevaSync acts like a Microsoft Exchange server and serves as a middleman between your phone and Google for bidirectional syncing of calendar and contacts. The service is currently in beta, and also supports syncing contacts from Plaxo.