I heard Tuta/Mullvad are quantum-resistant end-to-end encrypted and that Mullvad VPN is better at avoiding trigging captcha.
While Proton services are hosted in Switzerland which has the strongest privacy laws in the world and avoids the surveillance of NATO.
Exactly.
And yes, the handshake is made over an assymetric cipher, and then you use a symmetric one because they (this is not true for all symmetric algorithms out there, but the ones used in ssh etc. are) are both way faster and actually safe against quantum algorithms.