I have used quite a few before I stumbled upon linode and never looked back. I used rimuhosting and slicehost before.
I need the shell access as a root and I can say I never had my server rebooted in the las 2.5 years with linode. I rebooted it myself whenever I needed to but they never did. Support is just amazing and the total control you have...oh love it.
As for uptime and money back, I couldn't care less. I need uptime and access to it as ideally the server generates more money than 50 cents an hour.
I was also made aware of a new hosting company for Java apps.
http://jelastic.com/.
They claim to run any Java app.
I have only signed up with them but never had the time to properly play with it. Someone mentioned needing Java support for testing, this might be the place to go for free. I think the free account doesn't allow top level domains, but for testing one can get away with a subdomain.