Java Hosting Recommendations?

I’m looking to move the hosting of my sites and applications to a new provider and am interested to hear if anyone has any recommendations.
Ideally I want an environment that provides me with ssh access, Java and JSP/Servlet hosting through a private VM. I really want the freedom to be able to easily manage libraries and configure the web server myself. Access to a MySQL instance or other database is also essential.
If they’re Rails friendly too, then that would be another bonus; I’m playing with several applications currently and while Java is still my main development environment, I want to do some Ruby on Rails based applications too.
If anyone has any recommendations (or warnings!) please drop me a line.
Update: thanks to everyone who has sent in suggestions. I’ve had a lot of great feedback and there are a couple of services that stand-out. I’ll be sure to post a list of the suggestions. Thanks again.