From my experience shared web hosting accounts have the worst trust. You get the IP range of a public cloud provider, but you also share it with random people, that will send spam at some point.

So either get a package at some of those smaller providers with a dedicated IP, or go to one of the big providers (Google, Microsoft) and use their highly trusted IPs, that everybody whitelists by default.

I think you misunderstand. You cannot have a mail service on shared webhosting. It’s like 1999: Upload PHP using FTP, the end.

Instead, the hosting provider will operate a mail service for you, much like Microsoft 365, G Suite and the like. They will also take care of the IP reputation, SPF, DKIM and all.

Shared hosting does not typically run an external mail service. It's just Exim or whatever running on the same box as the shared Apache.

Maybe they do, but I would be surprised seing managed email sending in Hetzner's portfolio as part of shared web hosting. It's just not what that company typically has to offer, that's why I expected they just provide you the infrastructure, but ip reputation and so on is your problem. Taking care of IP reputation and successful delivery is a massive undertaking, especially if you let customers send whatever they want.

However, I dunno why people only mention the cloud providers, while services like MailChimp, Sendgrid and others offer this for mass emails and companies like fastmail for personal users. The cloud isn't really necessary at all.

The business for the web hoster is to provide me with some MBs for a website, plus a database, and also to provide me with some mailboxes on my domain.

Many small busineses have their 'online' presence like that. If I have mail deliverability issues, it's not my problem any more, I can call Hetzner. And before I started using it I was sceptical because if Hetzner did not fix the reputibility of their IPs or the spam from their other customers, it would be a problem for me. But so far, it worked quite well!