Are there different hosts I could try? Or am I better off paying for something like fastmail and using them as a smarthost?
I have two email servers running on Digital Ocean just fine - one set up in 2016 and one set up in 2021. It's a matter of doing the initial work to deal with the rejections - following the process the various hosts have set up. There will be a few block lists that you need to submit tickets to to have your IP unblocked. You'll want to create bulk sender accounts (even if you're not) with Yahoo, Microsoft, and Google. It's mostly superstition - "may this web form bring blessings upon my IP". Don't bother actually trying to check any of the reports in the UIs - only Yahoo sends emails to abuse@ for spam reports for small senders.
You'll want to join the Mailop list [0]. I'd say it takes about a month or two, mostly spent waiting, before you are in the clear and have perfect deliverability. Yes, it's annoying. Yes, it can feel hopeless. But it clears up pretty quickly. I've only since had problems with smaller providers and it usually gets resolved by contacting them.
[0]: https://www.mailop.org/ - I think people who work at Yahoo, Google, and Microsoft all monitor this list
You'll need an ISP who can permit traffic on port 25 (usually blocked for domestic connections); a "static" IP address really is necessary (a fixed address, not behind a NAT); and your ISP must be able to handle your reverse DNS entries (IPv4 and IPv6). Any ISP who can handle commercial customers will be able to do all that. And a UPS power source is highly recommended.
In some ways, email is a good place to start self hosting. It's based on store-and-forward, so you can be down for a while ... and when you come back up, any stored email will be delivered :)
But be aware of security, and don't let your server become a spam relay!
It's a bit annoying, but they do it to prevent people from using their infrastructure to send spam. And you only ever have to do it once.