You cannot solve this unless you send a pigeon or trust some higher power.
Certificates are a scam.
My solution which is convoluted and relatively insecure if you have a persistent MITM is to require a password change that you can encrypt with the old password, then the MITM has to remember the old password to know the secret.
But you are right that OTP only are safe after the secret has been shared. Just like all crypto including HTTPS and SSH.