I've been using DO for my VPN needs and it's been a very good experience. You can start a 5$ Ubuntu droplet, which is more than enough to host OpenVPN, and then configure your VPN manually. Check here :

https://www.digitalocean.com/community/tutorials/how-to-set-...

Or you can do it the easy way (but you won't learn as much) and run a bash script to configure everything automagically :

https://github.com/Nyr/openvpn-install