I like zsh, and I want to mention the fish shell auto-completion.

I start typing anything contained in a command in history (not necessarily the beginning) and can flip through the searches with up and down arrows. It is nicely highlighted, and the default, so I do not need to spend too much time fiddling with settings.