Lots of choices: managed hosting, EC2, App Engine; also unfair Sun criticism of App Engine's Java restrictions
I use a (semi) managed hosting company (RimuHosting) for customer and my own work: so much more convenient than running a co-located server! If a raid disk fails, I don't have to deal with it. I am also finding Amazon's EC2 to be a very low hassle hosting option (although Elastic MapReduce has given me some grief today but that was my own fault - once I learned how to use it, Elastic MapReduce is great). I have tried deploying one Java JSP-based web app to Google's Java version of App Engine - very straight forward and a fun experience.
One thing I read today that rubbed me the wrong way: Simon Phipps (Sun) was criticizing Google for restricting the JVM by not allowing some libraries. There are other issues like no threading and outgoing sockets that he did not mention. I totally understand why Google needs to protect their infrastructure by sand-boxing the Java runtime environment. (They had to do the same for Python.) Phipps must know this. Sun has announced recently their own "cloud platform" and it will be interesting to see if they restrict the Java runtime - if they don't I don't see how they can compete on price/performance. Can't live with Google's Java runtime restrictions? Then, use something more expensive :-)