Element for Android doesn’t support searching in encrypted channels
That's true of regular Element for Android, but it's being replaced with Element X (which is built with Rust). I would expect search to be added there if it isn't already.
and I think you can’t use E2EE in the browser at all(?)
I have done it in Firefox, so that's false. Perhaps you had trouble with a specific browser?
plus basically every other client has even more drawbacks when it comes to E2EE.
Nheko handles E2EE just fine, so that would seem to be false as well.
Since you're looking for recommendations, it would help if you said which clients you tried and what problems you had with them.