@Coyote no, it isn't. hard part is getting silicon valley fuckers to accept your mails :)
@Coyote i think the VPS/cloud providers all filter port 25. iirc, scaleway had an option to remove that filter.
tbh, you might be better off with a slightly more expensive small root server or a vps from a smaller company.
regarding domain names, i had no problems with gandi.net yet. they even have some offers for mail hosting. never used that though.
if you go selfhosting:
you don't need a mailserver for each domain. just setup one domain and add proper MX records pointing to this host for the other domains. all sane mail server software can handle virtual domains.
also remember that your server needs to have reverse dns set up, many servers check for this. having an spf record also helps with mail acceptance imho (there is much bullshit regarding antispam measures today, and i'm not 100% up to speed ;). to prevent receiving spam i'd always choose rspamd now.
debian is still surprisingly sane, even if it uses systemd now. otherwise, alpine or slackware? freebsd is fine too of course :)