What good solutions are there that prevent the age verification service and the website from comparing notes (because Big Brother told them to) and figuring out who you are and what you're doing?

If they voluntarily collude then yes, you can't avoid that. It's like third party cookies - once two parties collude it's game over. But that just outlines a situation where the user's chosen trusted service is hostile to their interests and they need to find one that isn't.

If Big Brother starts mandating the collusion - then yes, there's a hill to die on. But in some ways that's the point here. There are hills to die on - this just isn't it. And if you pick the wrong hill then you already died so you are losing the ones that really mattered. If the EFF pointed out to everyone that there is a privacy preserving answer to the core issue that is driving this, they could then mount a strong defense for the part that is truly problematic, since it isn't actually required to solve the problem.

This is only hypothetical for government ID's, but in theory government IDs could provide pairwise pseudonymous identifiers with services. Your ID with a single service is stable, but it is different with each service.