Jared Goralnick recently posted an excellent comparison between Microsoft's Outlook and Google's Gmail on Lifehacker.
Having recently shifted all of my e-mail to Gmail you can image which side I'm lean towards...though in all fairness I chose Gmail because I wanted all of my e-mail to be in the cloud and not because I thought Outlook wasn't for me.
I actually think Outlook is great. I don't like it's search capabilities all that much -- though maybe that's because we still use Outlook 2003 at work -- but otherwise it's got everything (and more) than I need.
That said, Gmail is awesome: I love everything about it and, now that Google is moving towards letting you bring some of its capabilities offline, I'm sure I'll soon like it even more.