Debian Wheezy

Can make it look more professional later.

Hardware and Hosting

Linux Core

The following assumes you have Wheezy installed and partitioned to your specifications - either by your host or by yourself via a remote KVM as above.

Software Stack

Unbound (1.4) - While I use a DNS service for my authoritative DNS servers, having a local DNS server is extremely handy. In addition to being almost a requirement for any mailserver, it can speed up some website functions immensely.
MySQL (5.5) - Getting the database going early is often a priority.
Nginx (1.4) - Webserver of champions. I do have some older documentation for Apache, but at this point I cannot afford to consider switching back.
PHP (5.4) - FPM and the ancient fastcgi method are covered.

Mail Setup and Stack

MySQL must be setup first for the following configuration, and a working DNS resolver such as Unbound is highly recommended.
Packages used: opendkim opendkim-tools spamc libmail-dkim-perl libmail-spf-perl libio-socket-inet6-perl clamav-docs clamav-freshclam clamav-daemon clamav-milter clamav dovecot-imapd dovecot-mysql postfix postfix-mysql postfix-pcre
1. We're setting up Postfix as a site.
Mail Setup (Wheezy)
Mail Tables (MySQL)
OpenDKIM (2.6)
Mail and DNS - Once we know what our domains are and have our DKIM key (from OpenDKIM), we can configure our DNS properly.
Spamassassin (3.3) - I've tried others, supposedly for the performance benefits, but honestly, with a handful of custom rules, and a solid postfix configuration, very little spam makes it through.
ClamAV (0.98) - Antivirus IMO should be approached from the viewpoint that it gives a chance for you to avoid the repercussions of your mistakes. Often a small one, but if not intrusive, still better than zero.
Postfix (2.9) - My preferred MTA of choice.
Dovecot (2.1)
Mail Reputation Management