Random ads are effectively noise. Targeted ads occasionally are of value. If there's going to be an ad, better it be a targeted one.
I also have no problem with companies tracking for the purpose of seeing which ads work.
I do *not* like the retargeting ads--if I didn't buy the item there's a reason! Either I didn't want it or I'm waiting for a better price, neither of which you're going to solve unless you're telling me about a sale on an item.
And the biggie is how intrusive they get. I'd like to see a system where the browser sends an acceptable-ad policy, a site can either comply or refuse to serve the page.