In Icicles you get such completion using S-TAB (by default - you can change the key, of course).
By default:
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, TAB or 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 C-( (for TAB) and M-( (for S-TAB).
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.