Also, a lot of providers accept cryptocurrency, which is trivial to anonymise.

I'll second Mullvad. Their interface is dead simple and the list of supported platforms/protocols is great. Quite permissive with 5 connections and port forwarding options. They actually detail how they attempt to never log the payment -> account link for most payment methods on their site. The account has no authentication, it's just an account number with no other identifying information.

They also list all their servers so you can modify your config to have any combination of servers/locations to use and fall back to.