I agree privacy is not a crime. However criminals like privacy, because it defects accountability. Hence, in the public eye, things that are highly private tend to attract criminal behaviour.
This can have the effect of guilt-by-association.
By contrast people do business either people they like. With people they trust. And both qualities require some level of not-anonymous.
Of course i do incidental business with anonymous strangers all the time - like buying gas, but even there the "company is a known entity to me.
If I wanted to use a messaging service that featured my anonymity I would need to trust the provider. Frankly I'd assume the service was being run by a state actor or law enforcement. (That would be true though even if you were public, and not suitably trusted)
Ultimately your service will be very appealing to both privacy-keen people, and criminals. This will result it people assuming that using it = criminal behaviour.
Take bitcoin as an example. Sure there are legitimate uses for it (beyond just speculation.) But the killer app for it is criminal enterprise. Personally if I encountered a service that only took bitcoin, I would assume its either criminal, or a scam or both. That's because bitcoin adds no trust to the situation.
Incidentally I don't believe privacy is a foundation of freedom of speech. Freedom of speech let's you say anything you like. Bur that freedom comes with accountability - in the sense that your words have more power when you put your good-name behind them.
Clearly though privacy and free-speech are very orthogonal -there are plenty of free-speech channels around. Privacy though is more complicated.
(Not least because when you privately communicate with an anonymous someone who ends up being a criminal then you open the door to being complicit etc)