Matrix's new key verification UX is incredibly intuitive. You press a button to verify the keys and then you out-of-band check that you're both looking at the same set of 7 emoji. This mutually-verifies both devices. I don't think it's possible for it to get any simpler.

With cross-signing, this will get even easier because cross-signed devices will be automatically trusted.