If you're on DO or Linode or similar, you start with a new VPS and check the IP it's assigned in all the RBLs and spam blacklists. (Google "multi rbl check", there's a bunch.) If it's on any of them, tear down the VPS and stand up a fresh one, and repeat until you get a clean IP. Then keep it that way by not running an open relay.

Beyond that, the main deliverability improvements, in approximate order of value, are: PTR record with the hostname you send mail from; DKIM; SPF; DMARC.

My mail server runs all of these, and I've yet to encounter trouble sending to anyone, including Gmail, which is often mentioned in threads like these as being a special issue. Admittedly I've been running mail from that IP since 2004, so have a long history of not being a spammer, but as long as you start out with a clean IP and keep it so, and make sure all your sender legitimacy boxes are properly checked, I don't see any reason why you should have undue difficulty.

(That's approximate descending order of value, to be clear. In particular, if you don't have a matching PTR record, you're hosed whatever else you try to do.)

Looking at the incoming mail in my server, I discovered that there are big legit mail senders who have a non-matching PTR. I suppose that at some point gmail et al stopped using that rule, or they just look for certain patterns in the PTR name, or something.

If you follow the basic steps of checking RBLs, using SPF and DKIM, you usually can do decent. I still have the occasional issue with hotmail/outlook/live mail though.

Another option if you just don't want to deal with it, but do want to run your own mail server is to use something like MailGun which can act as an SMTP relay and will be approved by those webmail providers out of the box.