For projects like this topic I don't really need AWS-level uptime, so I gladly go for the budget hosts. I run this project at Racknerd (good deals via Lowendtalk.com), and (so far) I'm quite happy with it. If I look at prices on their own site, it's much higher.
You could also go for RamNode, pay by the hour and less cheap, but from what I've seen RamNode has very solid performance too.
I don't think any of those are run from their garage

I also found out that several of the higher range VPS providers don't accept Bitcoin, or demand a copy of my passport (yeah, right!) first.

That's not a VPS, so won't help me much.