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?