In fish, you type "w" on the empty prompt and hit Up:

    > echo w̲ow

Hit return to execute, or any motion keys to start editing. As long as you don't move sideways, you can repeatedly press up or down to navigate history. The underline is actually a highlight hinting at the substring match in the line.

The difference is that typing an additional character after having moved in the history will start editing, appending the character to the line, instead of appending to the criteria.

What I miss in all of them is looking for a fuzzy match instead of a substring match.

I'm not sure how that is functionally different to mintplant's example?

In fish you just type 'w' hit the up arrow and then hit enter to execute or any motion keys to edit. The same number of keypresses as well.

Am I misunderstanding?

Discoverability. With fish i would have to type something that would be a good match to the command i want to re-run before pressing up. With bash i type ctrl+r and start typing and i can continue to type until it's narrowed down to the correct command.