2. Charge the user only the actual network fee, which would be very low ($1-$0.10). However, the problem is that we need to introduce a two step process to get an accurate fee: first create the transaction, then show it to the user for confirmation to accept or reject. Sometimes, due to high network traffic, the price can increase unexpectedly ($10-$50).
As customer, i would suggest this option. Aside from what @OmegaStarScream suggested, i would also recommend you to use fee rate which ensure the TX can be confirmed within next or 2nd next blocks.
Privacy based CEX? I am curious in knowing how it will operate.
I'd speculate it have similarity with exchange listed on
https://kycnot.me/.