For M-x I like smex. Like fuzzy ido but without the bugs and purpose built for M-x - it just works. smex persistently remembers how often you use different commands, and uses this to sort the initial list of completions - very handy.

  (require 'smex)
  (smex-initialize)                       ; is this needed?
  (global-set-key [(meta x)] 'smex)
  (global-set-key [(shift meta x)] 'smex-major-mode-commands)