In my experience, I would highly recommend Digital Ocean. Their experience is boiled down to what matters to dev's: simplicity and speed in setup. You can get started with a Droplet (what they call a dedicated virtual) for as low as 5$ a month for 512mb ram.
Go check them out and let us know what you think!
www.digitalocean.com