Debian Wheezy

Can make it look more professional later.

Hardware and Hosting

Some of the stuff here could be categorized under security, but the Core stuff here does not depend on getting anything else set up yet.

Unbound (1.4) - While I use a DNS service for my authoritative DNS servers, having a local DNS server is extremely handy. 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.

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