Getting openvpn working took about a day of hacking around on my vps and my mac. (just read the openvpn tutorial and follow the steps.) I still haven't gotten openvpn working on Windows but it's not something I've never needed.
I don't host my own server though, I use http://witopia.net I think I pay like $50-60/yr. But they give you a bunch of servers to connect to worldwide: http://cl.ly/2zEY