I manage several CentOS and Fedora VMs, and our setup is getting sufficiently sophisticated that it's time to move several resources on a single back-end VM, and serve those out to our Web VM, QA VM, Dev VM, etc. We trust our VM provider, but we don't trust every random stranger who can buy a VM on the same subnet for a few cents per hour. We need to encrypt traffic between the client servers and the back-end server. We have enough CPU headroom that symmetric encryption is no problem, but SSL handshake on each request would add too much latency, so application-level encryption is out of the question. We need some sort of VPN, but there are a lot of different ways to do it, and the numerous well-documented VPN configurations that are fine for attended client systems really don't make sense in this setup.
Which Linux VPN packages are best suited for this use case?
Which package-agnostic design principles should I keep in mind?
I'm not sure about your exact requirements, but OpenVPN (http://openvpn.net/) is easy to configure, available as a package in most distributions, works over either tcp or udp, has flexible routing options, and otherwise seems to meet your needs. I use it regularly as an "unattended" solution (comes up when the server boots, does not require human intervention).
An added bonus is the cross-platform (OS X, Windows, Linux, *BSD), which makes it convenient if you need to extend your VPN to your laptop/desktop/etc platform of choice.