If this is really a non-starter for advertisers, then mandating it will effectively ban advertising, non?
Remember: your business model is not sacrosanct! Disruption!
Just recognize that unless you do ban advertising, the result of this change will not be what's intended. The intended result is that websites, in general, stop tracking anonymous users. Instead, it will result in every user being explicitly tracked.
The most important issue here is that the political feasibility of reducing tracking of anonymous users is equivalent to the political feasibility of banning advertising.
(I'm slightly overselling here -- in reality, a good amount of advertising of the "sponsorship" form would still work. But the impact would be large enough that most websites would force login as I describe rather than stop tracking people.)
The result would likely be tracking via login as I describe, rather than true anonymity.
If you can't track uniques, you can't sell ads, and that's pretty much all there is to it. So there's huge incentive to undermine any scheme to prevent unique user tracking.
The solution is to somehow ban advertising, but that's biting off a bit more than simple user privacy.