The only real difficulty I foresee with users down the line is what happens when people lose their recovery keys.

Yep, the possibility of someone losing their recovery codes is a risk shared by practically all e2ee systems, authenticators, etc. (Have you backed up your Steam Guard recovery codes?) When a user is the only one with access to their secrets, they are also the only one who can be responsible for them.

This is part of why I suggested in my top-level comment that room admins coming from Discord disable end-to-end encryption when creating their first Matrix rooms. This keeps things simpler as their users get acquainted with Matrix, and reduces the consequences if someone loses their account recovery key. The point-to-point HTTPS encryption between client and server will still be in place, providing the same level of protection that Discord offers. End-to-end encryption can always be added to a room later, once everyone is familiar with the new environment.