Edit: The guide I was using had me on an old beta version. Current version works.
I did some experimenting with the low end VPS's on DigitalOcean and found that the minimum zcash could be built on there was the 4GB 2CPU VPS running Ubuntu 16.4.1 at $40/month.
Build went fine but after several hours of browsing every guide I could get my hands on, still zero connections.
Has anybody else tried this via Digital Ocean?