I use digital ocean. I've been rolling with centos with php 5.5, mysql 5,5, and httpd 2.2. I'm also looking into ubuntu 14.04 with hhvm 3.0 for my next server.

Note, this is for my personal projects, and there are better ways to deploy php code out there now, but digital ocean is great for development where I have lots of control.

A lot of people like Fortrabbit. I am using it for an internal project at work and it works well enough. Not perfect, but none of them are. http://fortrabbit.com/.

You can also manually setup your platform using Amazon Web Services or use their PaaS service Elastic Beanstalk.

I would def. check Fortrabbit first though. It is very compatible with Laravel and is setup for doing Git deployments and all that jazz. Plus, you can setup a free full-featured developer server. Only difference is that a dev server will "Freeze" after a couple days (depending on your setup you get extra time for things like using Git etc) and you need to login and unfreeze it.