More generally:
- I made sure my server's IP addresses weren't on any blacklists.
- I host my mail server with a reputable hosting provider (RamNode). Stay clear of companies like OVH that have reputations for poor abuse handling.
- I have configured SPF, DKIM, and DMARC.
- I registered my server with https://www.dnswl.org/, a whitelist for legitimate mail servers.
- I don't send spam or other bulk e-mail, only personal correspondence.
I also tried sending e-mails to a couple of people I know who use Gmail. I asked them to mark my mails as 'not spam' if they went into their junk folders. I don't know how much this helps "globally" in the Gmail system, but at least it'll teach Gmail not to mark my mails as spam for those people.
I had used my current personal domain for e-mail for a couple of years but I paid a company to host my e-mail for me. It might have helped that my domain had already built up a good reputation in big mail companies' spam filters, but who knows... It definitely helps, however, that my domain wasn't brand new. Newly registered domains are often penalized by spam filters. A poor choice of TLD can also hurt delivery: I know that many mail admins penalize or out-right block many of the new gTLDs like .top and .download.
I am not discounting those who complain about deliverability, but so far I haven't had much trouble with my low-volume, personal mail server.
Running your own mail server does require investing some time in learning the software, the protocols and all the ways spam filters will sabotage your attempts to send legitimate, non-bulk e-mail, as well as a little time for maintenance, but it's really not as bad as people say, at least in my experience. It's not something you "just" do, but it is doable.