You should check out https://github.com/tymm/directory-history then. It makes your history matching sensitive to the directory you are in. That means that commands will show up first which were typed in the directory you are in.

I don't want to miss this plugin and can't really understand why not everyone wants it. I guess I am a little biased though since I wrote that plugin ;)

I use C-r and C-s in bash, for incremental searching backwards and forwards. Takes less time to type these than reach across to the up and down arrow keys. Mind to stty stop undef to stop C-s from freezing your terminal, of course.

Zsh would probably be worth using, except for the fact that bash is almost everywhere, and I already know it very well. It's a tough one to call.

You can do it in bash too. I have this in my bashrc:

    bind '"^[[1;5A": history-search-backward'
    bind '"^[[1;5B": history-search-forward'

where ^[ is the escape character. This way, crtl-up goes to previous partial match (and up goes to last command as usual). I use it all the time.