You don't say what your company's current mail server solution is nor whether you need to achieve any from of compatibility, so we'll assume your needs can be satisfied with the standard components. You don't mention what your mail retrieval requirements are (for example POP, IMAP, MAPI), so we'll assume IMAP. You don't specify a requirement for webmail, so we won't discuss it here but you will be able to integrate one or more of the many solutions easily with the IMAP support.
Regarding the OS, unless you have an existing support team with Linux or FreeBSD experience your choice should be a pragmatic one, based on that which you have most experience and the ease with which you can obtain support or help if you have problems. Do you need a support contract with the OS? These should be the practical considerations which will help you determine your final choice because they will ultimately be more important than the differences between the OS's. If you will be the sole supporter and have little experience with both, I would recommend the latest stable Debian Linux because it is well-documented and is straightforward to get advice for common configurations of OS, mail server, IMAP server and firewall.
The choice of MTA is less clear and is often dictated by the available experience and recommendations from friends. Exim4 and Postfix do the same thing in slightly different ways. They're both well-supported, have similar features and are actively being developed which ensures that bugs and security advisories are responded to. From my own experience, Exim4 has sufficient configuration options to be able to support all but the most esoteric requirements. It's the default MTA for Debian and has excellent support from within Debian for the supplied Debian Exim configuration utility, and outside from the extensive documentation and mailing lists.
There's no substitute for hands-on experience, so I would strongly recommend setting up some local virtual machines to perform basic installations of OS and MTA. Once you've done this, you'll discover what questions remain unanswered, based on your setup requirements. It will also give you an opportunity to experience and configure related software, for encrypting mail transfers, for authentication, for spam and virus filtering and for general server security and backup options.