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.
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.
Cookies are for session management; the central problem with cookies is that people feel that servers will treat certain sessions as ephemeral, but instead those servers track these people for a long-term creepy analysis. One connected problem is that many sites require cookies in order to show public content. Public-content sessions should be entirely ephemeral, meaning that you shouldn't need a cookie in the first place. (The New York Times offends in this regard egregiously and persistently.)
You can easily comply with the EU law by either placing the notice on the login page or else not storing cookies. This means that anybody who abuses cookies in the above way needs to be loud about it; "we're not giving you an ephemeral presence like you think!" -- which actually not only fixes this problem but also creates an incentive to not abuse cookies in this way.
I am not saying that we should abandon sessions entirely, but that it would be nice if the 'default' session treatment followed the rules that online banking uses: when the browser is closed, all sessions are done. If we did this then we'd want to include a 'persistent login' mechanism, which would take the form of an in-browser 'would you like to sign in?' dialogue accompanying a web site. This means that unlike current HTTP authentication, it would have to be somewhat asynchronous; you are shown the ephemeral version of the page while the browser itself requests you to confirm that you want to join your long-term session there. (I was originally going to recommend that the browser just handle a digital signature scheme, but of course that does not solve the 'logging on to Facebook from your sister's computer' problem easily. Hm.)