I hope this doesn’t come across as an insult as you’ve already expressed your dislike for Outbrain and Taboola but you’ve stepped right into their market and have a huge opportunity to shake things up.
I’d say you’ve figured out what every publisher loves - or should love - keeping traffic and keeping the audience engaged. I assume most smaller publishers >10m views would make more money keeping readers clicking around their own site several times compared to losing them to a “click-bait” sponsored content ad.
I would however recommend after spending a decent amount of time on your site to take a look at Taboola and Outbrain - the copy and design of their sites are very to the point and informative - to publishers and advertisers. I don’t really get that from your site. I’d try to be more like them in those areas - they have a knack for grabbing both publishers and advertisers.
As for getting the advertisers, get on LinkedIn - search for people with job titles like Manager of Digital Marketing - poke around their profiles see if their company might be a good fit for you then fire them off a quick email.
Just my two cents!