Nowadays I'd generally go for hosting providers that have been around for some time.
Hetzner: has both great features and affordable costs (I needed to verify my ID, though)
Contabo: the prices are great, but the performance is a bit worse than other options
Time4VPS: a Lithuanian provider that I used due to them being cheaper than Hetzner, unfortunately their prices have increased noticeably, only the yearly plans are worth it
DigitalOcean, Scaleway, Vultr: all have good features, but can be expensive
Azure, AWS, GCP: too complex and enterprisey for my private needs
That's not to discourage anyone from using them; in fact, LEB VPS servers are pretty much all I use (each being ~$25 / year), and I've gotten quite good at keeping useful, tested backups, keeping redundancy in my services, and being able to stand up a new server quickly.