I've had a box at Serverbeach for a few years, and they've been very reliable, and are pretty cheap. There's been a single issue I was unhappy about, which was a mandatory IP change for my box due to a reconfiguration of their network (after they were bought by peer1, a fiber/bandwidth company).

All else has been nigh on perfect. They do expect that you'll handle everything yourself that can be handled remotely, though I wouldn't think that was a problem in this crowd. :)

Edit: Er, and if you do choose to go with them, email me for a discount code if you want one.