I've used PowerVPS (
http://www.powervps.com/) in the past and they've been good for me. I was on the cheapest Webmin Linux plan and it ran a couple boards smaller than this one. You might have to go with the 2nd Linux Webmin plan for this site.
It looks like they've changed their packages though, they don't have Webmin on there anymore.
I didn't have much downtime. There were a couple times when a server would go down for a few hours, but it wasn't very often.