Like @doofus, I'm using Digital Ocean for something small now, and it's really really slick. However, it's relatively expensive; it would be prohibitive for your use case, unless you're loaded, but even then they don't take btc.

I've been quite intrigued w/ Hostinger, which is astoundingly cheaper, and they also take bitcoin. There's a lot of bullshit scam VPS companies, but Hostinger seems to have real (non sock-puppet) endorsements. Planning to try them out when my two month freebie from DO expires.

Would also be interested in other perspectives.