This code puts the recent commands at the top as well,
but probably it needs to be opt-in:
Makes sense to me, and, yes.
FWIW, the minibuffer.el code already uses this kind of sorting for the
list of completions used in things like `icomplete` and
`completion-cycle-threshold`.
For *Completions* the sort was kept alphabetical so far because that's
also useful (for example in the case of M-x completion, it makes it
easier to skip over blocs of commands sharing the same prefix).
So, while I think it can be useful to sort by some kind of "guessed
usefulness" such as presence in the history, I don't think this should
be forced by the completion table of commands.