No stalking - the ads should either be tailored to the currently visible content, or the user should be allowed to select which kind of ads they want to see.
Accountability - the service showing the ads shares some responsibility if the ad or advertised product ends up malicious, fraudulent, etc. This means services will be much more selective in which kind of ads they show, inline with print magazines & billboards (you usually won't see malware or scams in magazines because their reputation is on the line).
Transparency - the details of who paid for the ad, and the targeting criteria (if any) should be clearly displayed. Also, the service should provide a page where users can browse & search all ads (not just political or sensitive ones) that have ever been published on the platform.
If ads followed the model I'm suggesting there would be much less reasons to block them. I don't hate ads per se, I just hate scams, annoyances and stalking. If I can actually choose which ads I see and have some guarantee that they aren't scams I would actually engage with the ads.
Print ads aren’t bad and in fact people are happy to buy magazines with the idea that there are ads in there. In fact, ads are IMO part of the magazine experience and allow you to discover new products.
I personally would like to see ads as long as the points I outlined above are met.
Instead, the ads should be done in such a way that most people don't have any incentive in blocking them (I personally would like to see ads provided that 1) they are vetted and 2) they are for products I'm interested in, based on the choices I make in my profile). Given that, the few outliers that would still end up blocking them wouldn't be a problem worth solving (you can always offer a paid tier to remove ads for the people that truly don't want any ads).
Word of mouth. Reviews by third parties that don't have any conflicts of interest and which list your competitors and how their offerings compare to your product.