Then those websites should be considered broken much like we consider Adobe Flash and sites with invalid TLS certificates.
Make it a long deprecation if you have to. Give even longer exemptions to the really big players / the big breakage / the legitimate use cases while we find better ways. But it is up to the browser vendors to remove the weapons here.
It's possible for your IdP to track the SPs you authenticate to regardless of protocol or cookie use, of course.