^R is more powerful, though; it matches at any point in previous commands, not just at the beginning.
> The lack of this functionality actually really kills my ability to use any other shell.
You can achieve that behavior in readline (which is used by bash, python shell, etc.) by changing the up/down arrows from previous-history/next-history to history-search-backward/history-search-forward. In ~/.inputrc:
"\e[A": history-search-backward
"\e[B": history-search-forward
Note that you can still use ^P/^N for previous-history/next-history (or you can remap "\C-p"/"\C-n" as well).