Google Contacts sync with iPhone 3G (iOS 4) without EAS
I ended up using the iTunes sync feature ( http://support.apple.com/kb/ht1296 ) with Google Contacts.

It works pretty flawlessly, with the only (huge) downside that you can't sync without the PC.