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