I'm a fan of Apple's MobileMe service because of its OTA contact and calendar syncing and cool features like Find my iPhone and Remote wipe -- although, thankfully I haven't had to use the latter two.
The problem with MobileMe is that many users bristle at the thought of paying $99 per year for anything, especially when they can be done for free.
Wired magazine has a piece in its September 2009 issue on how to Sync your life with Dropbox. Dropbox is a free online storage service, that allows you store your data on the cloud and access it wherever you have Internet access.
The Wired tutorial explains how to use Dropbox to sync your iCal data on two computers -- for free. It involves a little Terminal chicanery, but if you're not afraid of the command line, you could save yourself a couple of bucks.
If you're looking for online storage that is accessible from the iPhone SugarSync and iDisk are also available as free apps while Dropbox is available as a Web application for the iPhone.
Anyone tried it with contact syncing?