Ctrl-R is by far the most useful one for me.
"\e[A":history-search-backward
"\e[B":history-search-forward
Type a few characters and hitting the arrow keys will show only commands that match those first few characters.It's so ingrained I had to actually do it in a shell to know what it was I did.
I can't replicate it now on my test box; it works exactly the way you say it should. It may be a terminal issue; I'm currently on Windows using cygwin to ssh to Linux.
This might be a zsh thing though.
Also, other emacs keys work like back: ctrl-b, meta-b, forward: ctrl-f, meta-f, start of line: ctrl-a, end of line: ctrl-e etc.