I agree, and some days ago, in another thread, I got +10 on my comment detailing this shortcut.

Another no-brainer imho is editing you /etc/inputrc or your $HOME/.inputrc and bind keys (usually PgUp and PgDn) to history-search-backward and history-search-forward.

From there you can navigate your history like with the arrows, but it will only consider lines that starts with the string that is currently on the command line.

It is a MUST.