In Icicles you get such completion using
S-TAB (by default - you can change the key, of course).
TAB gives you prefix completion. (Or vanilla Emacs completion - e.g.,
*insert TAB will do as @abo-abo indicated.)
S-TAB gives you "apropos"-style (i.e., regexp) completion, which of course includes substring completion.
Just use a different completion key,
S-TAB, to get a different kind of completion. And for each of these keys you can use different completion methods, including various fuzzy completion methods. You can cycle among the methods using
All of this is true not only for
M-x but for everything - any minibuffer input completion.
And BTW, Icicles does not "steal" your
M-x key. Whether you keep
M-x bound to standard command
execute-extended-command or you bind it to Icicles multi-command
icicle-execute-extended-command is up to you. And in either case you can take advantage of Icicles completion when
icicle-mode is turned on. (If you turn off
icicle-mode then you are back to vanilla Emacs behavior, for
M-x and for everything else.)
By default, you do get special multi-command behavior for
M-x, but it is trivial to customize option
icicle-top-level-key-bindings to choose which keys you want to have take advantage of any special Icicles commands.