Personally, I like XMail, we use it to manage the email for our small domain.
It can be found here:
http://www.xmailserver.org/
It's an opensource mail server, and runs under linux and windows. I can't speak for how well it runs under linux, as I run it under Win2k Pro, but I image it runs just as good, if not better. I haven't had any problems with it at all, and it is updated frequently by the developer. The setup is a little tricky, requiring the modification of text files to configure the server. I would suggest reading the configuration sections of the documentation, which is excellent for free software. There are also many examples for configuring your servers.
The only disadvantage I've found so far is that XMail automatically runs POP3, SMTP, and Finger servers, whether you want all of them or not. This isn't too big of a problem as I simply block the Finger server at my firewall since I don't want it.