Now I use DigitalOcean's $5/month box running CentOS.
For most things though, you can just use ssh, no setup on the server required. You just need putty, or another ssh client on your local computer.
Nice guide for putty here: http://www.bestvpnservice.com/blog/how-to-setup-putty-for-ss...
For command line ssh clients, things are much easier. Just go:
ssh yourhost.com -D 8080
and then set up firefox to use a 'socks proxy' at localhost:8080, like the firefox part of that putty guide.