Seconding `fzf`, it's such an improvement from the stock Ctrl-R behavior I think it's worth installing even if you never actually run `fzf` at the command line itself. Hence why I led with the new shortcuts at https://andrew-quinn.me/fzf (fuzzy `cd` with Alt-C being the other one of note).
Interestingly, the default fish shell also comes with something similar these days, although I still prefer the look of `fzf`.
I switched to atuin and it's a huge step up from native Ctrl + R and fzf because you can press Ctrl + R again and again and it switches between searching through directory, session, host, or global history.
I listened to an interview with the creator of atuin on the changelog podcast. It seems like a compelling idea. The only thing that makes me consider switching from the fzf/ctr-r combo is syncing my history between tmux sessions. But I don't spend enough time in the terminal to really justify the time to set it up.
Came here to say this. Fzf is almost too good, it's so convenient to find past commands that I've gotten two years into a career as a software developer without committing any of my most common command line tools to memory.
Interestingly, the default fish shell also comes with something similar these days, although I still prefer the look of `fzf`.