You can't do it reliably without a static IP in a non residential subnet that lets you set reverse dns. If you have a static residential IP and they don't filter inbound SMTP you can make it work with a smarthost/relay like mailgun. Its not the insurmountable obstacle everyone makes it out to be, but its not going to be free unless you already have an IP that meets the criteria.

If you don't have a static IP you need will want to think about a MX relay service too ~ although mail is surprisingly tolerant of offline MX hosts if you can wait a little bit for your mail.

I have access to a commercial (non-residential), fixed IP. You could also use an outgoing relay as a compromise, since presumably the issue you are facing is other servers rejecting email that you send from a disreputable IP. That being said, you really want a fixed IP as a matter of convenience if you are going to self-host anything.

A VPS or cheap dedicated is enough to get the static IP. I have very few problems with email, I use one VPS and one dedicated server though some zealots would argue a vps isn't self hosting