I am currently running all my browsing through a self-hosted VPN on OVH's cheapest SSD (GBP £1.50/mo on Black Friday), and I'm happy so far. Bandwidth is limited to 100Mbps, but my home connection is 55Mbps, so no problem.

In fact, one thing this highlighted for me is that Linode disables AppArmor on their kernels (running Ubuntu 16.10) — which seems like a slightly shitty thing to do, especially for a company with a somewhat flaky security history — whereas OVH doesn't.