I've also been considering getting a VPN service. I run OpenVPN, in order to get to my home network while away. I've found a service, and one of the VPNs they support is OpenVPN. But I've heard that OpenVPN isn't that great in terms of performance. It doesn't matter now, because I don't push that much traffic through it.
But if the VPN is becoming my default route, performance will be much more important. Which has also let me to realize that I'll probably do somewhat messy routing, letting primary sites go directly out, while "other stuff" goes through the VPN. I don't care if advertisers know I visit Slashdot or Ars Technica, nor if I go to Amazon. It's all of those other links, like non-Amazon shopping or medical searches. Who cares if they watch me downloading OSS to compiler for Gentoo?