I really, really don't like completions as a feature in virtually any shell. I much prefer reverse search.

Have you tried fish? You can partially complete the query and use the arrow buttons, and the search is fuzzy if you use the previous commands search. Typing Sudo for instance and arrow will show my previous sudod commands.

Yup, its great. Problem is, the syntax is slightly different from Bash. So whenever I use a shell script or use some kind of commands where the differences are incompatible, I tend to switch to Bash. And then my history doesn't add up with the one from Fish.

For fuzzy search I bound ctrl+r to fzf (you can use Rust's sk too).