Hotmail matches all of that and adds synchronization support for tasks as well. Before you rush to configure your device though, make sure it is supported. Like Google Sync, Hotmail has limitations on platform support. Complete setup instructions are at the Windows Live Solution Center.
Windows Mobile 6.1 and 6.5 are officially supported, though I'd wager if you were on an older 6.0 or even 5.0 you might have success in getting it connected. I actually have a 5.0 device at home in a box somewhere I may try just for kicks if I can find it. Windows Phone 7 is also on the officially supported list so if you have one of those phones on your wish list, you'll be ready to go day one.
The iPhone, iPod Touch and iPad are also supported for everything except tasks. Nokia support is also there and like Windows Mobile/Phone, tasks are supported.
Android users are a different story. Hotmail is currently testing devices, and with Android, that means several different version of the platform. They do note on their setup page though that some users are having success with Android 2.2 with the default application or the Touchdown app. If you can get it to work, great; if not though it could be a month or more before testing is finalized.
Where this really shines is on devices that support multiple Exchange server accounts and you may already have your work account set up. You no longer have to relegate your personal email to IMAP4 or POP3 accounts. If you've never given Exchange Activesync a try and your device supports it, try it out. I can guarantee you you'll never go back.
Two of the biggest free email providers now support Exchange ActiveSync for mobile phones. Yahoo! remains the holdout. Yahoo! has a number of clients or webmail which work on some devices, or a $19.99 annual plan that allows POP3 access on any phone that supports it, but none of those solutions match the simplicity and functionality of Exchange ActiveSync.