I prepayed for a 3 year reservation for a small Amazon EC2 instance and I am very happy with that decision because I frequently deploy customer projects to AWS, and any experience from my own projects is a big help.

I also permanently rent a small VPS from RimuHosting. I like their customer service and their low costs.

And, the elephant in the room is Google AppEngine. I have several deployed apps and an effective price of free is difficult to beat. Surprisingly (to me) I have had no customer interest in deploying to AppEngine. I have had ongoing problems using JRuby+Sinatra on AppEngine, but the Java support is fairly much hassle free.