I've recently migrated from Exchange with great success. I don't know wether a webbased client is acceptable in your case, but I have to say Group-Office
is quite a brilliant solution.
It's GPL-ed, allthough an officially supported version is also available. It has all the functionality you mentioned
shared and private agenda; shared and private contacts, private mail, todo list
You can use any IMAP/POP3 solution as an e-mail backend. I use Postfix w/ MySQL and Courier IMAP.