Ctrl-R and Ctrl-S please. Using the arrow keys for searching through history quickly (i.e. without leaving the home row) sucks.
eval (cat ~/.local/share/fish/fish_history | grep 'cmd:' | cut -c8- | fzf --tac)
and then I simply bound it with `\cr`. It doesn't exactly replace Ctrl-R functionality but it suits my need.