I highly recommend using a debian-based VPS and hosting through RIMUHosting. I've gone through several VPS providers (VPSLink and such) and they have all been terrible as far as uptime and provide no support (as advertised). I've also gone the shared hosting route and have been dissatisfied with the level of access, quality, uptime, and service.
RIMU has phenomenal service. They are not a managed VPS per-se, but they sure do act like one. They helped me configure Tomcat as a service, they helped tweak Apache, they installed my JVMs for me, and they helped me set up Varnish cache. They also have a lot of people who host Java with them, so they know a lot about setting up standard Java architectures and front-loading with Apache.
The great thing is that they always respond quickly no matter what time of day you e-mail them. Even when they change shifts, the new support person picks up right where the last one left off.
I'm going on and on, but I've been truly impressed with their knowledge on Java and their level of support, at pretty much the same price as any other VPS.