They do already, and big companies have already been fined for not offering them, which led to some smaller parties adding them. See here [0] for a list, amongst which was Microsoft getting a $65 million fine for not having an easy opt-out on Bing, or $162 million to Google for the same thing. Noncompliance should be reported.
[0] https://www.cookieyes.com/blog/cookie-consent-fines/