Use an IP where it's unlikely that the last tenant sent lots of spam (budget hosters can be troublesome; don't use consumer DSL; steer very far clear of AWS.) There are sites that allow you to query all major blacklists at once, which may prove useful. Don't worry too much about SPEWS listings, though - they are sufficiently trigger-happy that few hosts will reject your mail
just for appearing in SPEWS.
You'll want to point mail.$YOURDOMAIN at this IP, and set up reverse DNS (pointing to mail.$YOURDOMAIN; some hosts check for the "mail" name.)
Start by setting up Postfix (this setup is based on my own of a few years back, and by no means the only way!) Then, when you get annoyed with spam, add countermeasures in this order: postgrey; setting up some Postfix restrictions (no unauthorized pipelining, etc.); blacklists (Spamhaus' ZEN list was good a few years back); dspam. You may want to add clamav for virus filtering if you have non-technical users. You may need to set up amavisd to get clamav working, but I found that amavisd didn't filter all that much more spam than a properly-trained dspam, so I'd start without.
At some point, something will go wrong and you'll lose mail, or receive it much later than you wanted. Add monitoring to fix this - pflogsumm is good to check for mail that shouldn't have been rejected, something like the Simple Event Correlator can monitor your log files, and something like Nagios (or one of the commercial services, Pingdom/uptimerobot/...) can detect when your host goes down.