With DigitalOcean you can install a droplet just the way you like and save it as an image so you can create new droplet from it. It's a little more work than Heroku, Pagodabox or Fortrabbit but way more flexible and cheaper in my opinion.

ps setting up a mail server is way to much work, mailgun.com and mandrillapp.com are super cheap and really easy to setup

I would highly recommend Cloudways here. Why? because it gives you great flexibility in managing multiple client websites easily through its powerful console. They provide you the choice of choosing 3 cloud providers like DigitalOcean, Amazon or Google Compute Engine. What I love about Cloudways is that they have taken away a lot of pain from server management by providing a managed hosting environment.