I will not consider exch as CEX or DEX either, its both of them, or probably a hybrid one that operates without KYC and don't hold user's funds.
eXch is a CEX. An instant but centralized swap service. They have control of your coins until they get sent to your personal address. There have been instances where the swap service doesn't go through due to issues with their Ethereum server, for instance. In such situations, eXch has the money and you have to get in touch with them to resolve the problem. They were reputable and didn't cheat or steal from their customers, that's why people didn't mind it being centralized and not trustless.
How can a CEX exchange protect user privacy without running into legal issues? This is going to be difficult. Preferably, your real identity shouldn't be known and there shouldn't be a way to discover who you or your team are. You should also operate out of a jurisdiction with lenient laws and a 'fcuk you attitude' towards US and EU law enforcement inquiries. You must also find a way to keep your website safe from being taken down by law enforcement and not get DDOS attacked, which is easier said than done.