In Windows, I currently use WiTopia's VPN, which is cheap ($60/year), solid, and fast. It's so fast that I leave it on all the time. It lets you pick a gateway in your choice of about 40 different cities around the globe. Unfortunately, it is not available for Linux.
WiTopia doesn't support Linux directly, but it seems it's possible to use it with Linux. http://wiki.witopia.net/wiki/Installing_personalVPN-SSL_on_Linux
If you decide to look for another VPN provider, anyone who supports OpenVPN should work in Linux.