I think they mean anonymity from the ISP/phone maker/app. Merely exchanging certificates in some trusted manner first turns your anonymity example into the privacy one.

And cert management is probably 'just' a UX/education issue at this point

You need to be careful with that, because anonymity reduces privacy.

Let's get rid of Eve for a moment.

Say Alice has a secret that she loves tomatoes, she wants to share that secret with Bob.

She can go to Bob and whisper "I love tomatoes" in his ear, in this case Alice has high degree of privacy because she knows (or has very high confidence) she is talking to Bob, she can verify that they are alone and take additional precautions, in this case she also shares the least information possible needed to convey her secret to Bob, and is not forced to share any additional information.

Say Bob has a secret that he's scared of Flamingos, he wants to share this secret with Alice.

Alice is away on a trip so Bob and Alice use an anonymous messaging app.

Bob now effectively has less privacy because the level of privacy is directly tied to the confidence that Bob has that he is talking to Alice, Alice also has less confidence that she is talking to Bob. Bob can't know for sure he is sharing his information with Alice, and he doesn't know if the party that received that information would respect Bob's privacy, Alice doesn't know for sure the information came from Bob and she might not know she needs to keep that information a secret.

If Alice and Bob share additional information to prove their identity the level of privacy is also reduced both because they had to create additional identifiable (and hence private) information, and they were forced to share information beyond what is needed hence losing agency over what information they would like to share.

The 2nd thing many people confused or mix anonymity with is "deniability" (to an outside observer) or the fact that one cannot prove that 2 parties have exchanged information; in this case anonymity is again a problem since a system that is truly anonymous whilst providing deniability does not provides privacy, and a system that is not truly anonymous whilst providing some privacy does not provides deniability since it forces parties to exchange high confidence identifiable information in the process.

You can have a system that is (~)100% private and is (~)100% deniable for example you can have a network of nodes in which all nodes talk to one another at a constant rate the information is either fed from the node operator when they want to send a message or from a random source and all traffic is encrypted so your information is both private and deniable.

Another setup is some sort of random path routed network similar to TOR or any other onion/pass-the-package router in which when a node sends a message to another node that message would go through a random number of nodes and no node but the destined one would know if it's the final node or not, if nodes on this network are also authenticated and the messages are strongly signed this would both provide deniability and privacy.

Now likely there aren't non-theoretical solutions that are 100% of anything, but people really need to stop relying on anonymity for privacy, in the worse case you have no privacy because you don't know who you talking too, at the best case you have no-anonymity because you have to generate and send identifiable information which also reduces your privacy.