As long as it's not terribly mission critical I'd suggest a VPS. Since you have a virtualized server you get everything you mentioned (and the responsibility of keeping the damn thin up to date). Take a look at http://lowendbox.com You're likely to find deals in the $20/yr range for small instances with ~128MB RAM. Expect 99% uptime and you'll be pleasantly surprised with the third nine.
If you chose a supplier at random, they yes, some of those will probably disappear after a few months. But if you spend some time digging around a little, you'll find things like "Best Provider of the Year" type posts (e.g. http://www.lowendbox.com/blog/best-low-end-providers-in-2011... ). These tend not to be fly by nighters.
Consider starting with that list, and look for recent offers by them. Also read the comments on each offer looking for irregularities. Lowendbox has a decent community, they know when an offer smells, or when a fly-by-nighter drops in. Granted it won't be perfect, but you can reduce the risk of a provider disappearing all of a sudden with a little bit of reading and digging.
Two in particular I find trustworthy: VooServers and Evorack
But beware, many low-end-box type providers use stock standard off-the-shelf tools and software, including WHM. So if you have a religious disagreement with passwords in cleartext emails, you should steer well clear of lowendbox/WHM combinations and go for a highend supplier instead.
Or perhaps a more practical method, don't use a secure password when you sign up, and make it more secure on the VM itself when you log in for the first time
I didn't end up playing with any low end VPSs because none of the providers I evaluated offer users the ability to clone VPSs, which is one of my requirements.
That's the nature of the business I'm afraid. But I have found some reliable hosts through the site and some very established hosts used to make offers before the siteowner left.
