Is this possible? and can it be as seamless and transparent as using MobileMe?
Google actually uses the Microsoft Active Sync Protocol that essentially turns your GMail account into a Microsoft Exchange type of account.
You can do this easily with no additional software. Just follow the steps outlined here on Google's site. I use this to sync my Google Contacts and Calendar. It works very well!
Edit: Please note that this currently only works for Contacts and Calendar and does not sync your email. You will have to set up your email separately.
There's an option in iTunes to do this. It's where you set contacts, you can select Google contacts, and provide your login/password. This works fine on a PC, most likely Mac too.
It did throw in a ton of junk contacts for me too though; lots of one-off addresses that I used once showed up. Took a while to delete all that, but now it works great.
I have used OggSync to do this before Google offered support directly. I have been very pleased with Oggsync.
I have been using the free service of Nuevasync for both Google Calendar and Contacts for almost a year now, and I can recommend it. Works like a charm, better than Google native stuff.
Google Sync will give you seamless and transparent contact syncing between the iPhone's native Contacts app and your contacts in Google - it will even sync photos you've linked with your contacts.
It will pull down all the contacts in the "My Contacts" section of Google Contacts, so it's best to make sure you've got that exactly how you want it before syncing.