When using a Mac as a main computer, I was able to create an overly complicated setup that would allow me to sync my iPhone wirelessly with Google Calendar/Contacts. But this doesn't work on my linux computer. When I was looking foa a solution I found a link to NuevaSync.
NuevaSync is a Exchange "proxy" for Google Calendar/Contacts. This allows the iPhone to be configured to sync to thie Google apps. This solution acually makes MobileMe unnecessary. This article has a good walkthough for configuring NuevaSync with an iPhone.
This has been working fine for me on my iPhone.
One problem that is being worked on is better support for multiple calendars. Also another annoyance, with the iPhone and not with NuevaSync is that you can not connect to multiple Exchange servers. I would like to connect to my work's Exchange server for mail, but connect to NuevaSync for Calendars and Contacts.