> Even the current version of Emacs doesn't do fuzzy completion for M-x commands, just start-of-token completion; out of the box the completion is a little basic. I know there are packages which make this a lot better, but you have to know about the packages. :)

This is not quite true.

The minibuffer, which is what vanilla Emacs uses for M-x command completion, has a set of completion styles, ordered by preference. You can find the full set of completion categories supported by Emacs in the variable completion-styles-alist. Among those is one called flex, which allows for full fuzzy matching between provided tokens.

This is not a default minibuffer completion style, but it provided without additional packages. One would add it by adding it to the list of completion styles used by the minibuffer as specified by the variable completion-styles. I recommend trying it out.