I've ran a VPN via Amazon's AWS "free" tier (approx. $5/month for 12 months). Works both on Windows (with appropriate UDP encapsulation configured for IPsec traffic[0][1] on both client and server) or via OpenVPN on Linux.

I'd imagine OpenVPN would work just fine on Linode or DO. And Windows/OpenVPN would also work via Microsoft's Azure platform.

[0] https://support.microsoft.com/kb/926179 [1] The key term to Google is: "AssumeUDPEncapsulationContextOnSendRule"