Sendmail is fine, and I think it gets a bad rap. Of course it has had more security issues come to life than others because its much older and much more widely used. Just stay up to date, and you'll be fine.
Many people rave about Qmail. I tried running it, but I didn't like it. The daemontools package that it requires insists on putting its directories in the / filesystem, right at the / level. That sucks. I've really tried to like it, but its never grown on me.
Postfix is a really good drop in replacement for sendmail. The configuration is quite different, but any software that ran with sendmail should work with it. It is also designed to do less stuff as root if possible. I've used it before with good results.
I'm getting ready to start messing with Exim. Exim is supposed to be really flexible, especially with integrating with spam filtering (RBLs, etc).
Another thing that you'll need to decide on is what type of mail storage you'll be using. mbox is the format that sendmail, postfix (I think), and Exim use by default. Qmail does maildir by default. Your choice of POP3/IMAP daemons will be affected by this choice.
Check this link out for a quick comparison:
http://www.geocities.com/mailsoftware42/