Use GiftWrapped DMs (https://nips.nostr.com/17).
Discussion
Is it just a matter of time for devs to implement in clients? Or is it a matter of users choosing the right message or relay type?
Both. Not all clients have implemented NIP-17 yet, and some relays are also not handling gift wrapping correctly. For example, I recently updated Haven to accept Gift Wrapped messages. My suggestions are to use 0xChat and Amethyst (make sure to click the "Incognito" icon on Amethyst to enable Gift Wrapping).
For relays, I'm currently using:
wss://auth.nostr1.com/
wss://relay.0xchat.com/
And my personal Haven instance.
They are all NIP-17 compliant.