Hetzner is hands down the best when it comes to performance/price ratio but since you ask this on Bitcointalk, I assume that you are looking for a hosting provider that doesn't ask you to submit KYC and also accepts cryptocurrencies as a payment method.
It's also worth to mention Hetzner doesn't allow their customer to run cryptocurrency software where there are few cases where they kick customer who run altcoin full node.
I have bad experience with them, as my registration were rejected for no actual reason after giving my card and personal details. I don't know maybe my address as i'm Asian as i read some redditor discussing they don't accept outside EU countries and US, idk if its true.
I suggest for cheap VPS as i currently use Ultahost starting in $5/month and much cheaper if billed annually, i don't experience downtime yet for several months now.
They accept people outside EU countries and the US. To be more clear, I'm from a country that's transcontinental, it's located at the intersection of Eastern Europe and West Asia. We aren't officially part of the EU but they accepted my documents without hesitation.
Why did they request an address from you? In my case, ID documents were enough. Btw I always have problems with companies that request address verification from me because in my country that's impossible, I am not officially registered anywhere and when you rent an apartment, it's also done unofficially, so bills come in the name of the official house owner and not at the name of rentner. It's nowhere recorded that I rented an apartment.
Btw try Hetzner again, their prices are unbeatable or if you still have issues with them, try to look for Hetzner resellers. In my country, there are many Hetzner resellers that offer very good prices. There might be some Hetzner resellers in your country too to have access to local support or probably look for them somewhere else.