Softlayer and Linode for hosting.
Rackspace Mail for mail.
Why not run your own mail server? Outbound deliverability is a pain. You can't just install an SMTP server package and go -- you need to think about DomainKeys, SPF, DKIM, Sender-ID, monitoring realtime blacklists for your IP, etc. That's a whole job unto itself and is worth paying a couple bucks for someone else to do it.