I used icicles for a while... I found it to be pretty good. However, it's pretty invasive, and tended to slow things down a bit on my machine. I also found it to be a bit heavy in the way it requires me to interact with it. Specifically, it seemed like every 20 seconds of interaction or so I'd get slapped in the face with a new window asking me to make a choice.

I think if I took the time to really configure it, remap keybindings, and write helpers, I'd probably end up with something I like. However, I found it much easier to use ido for everything:

(require 'ido)
(ido-mode t)

;; use ido to complete commands via M-X
(global-set-key
 "\M-x"
 (lambda ()
   (interactive)
   (call-interactively
    (intern
     (ido-completing-read
      "M-x "
      (all-completions "" obarray 'commandp))))))

;; Maintain a list of recent files. C-x C-r to open from that list
(require 'recentf)

;; enable recent files mode.
(recentf-mode t)

; 50 files ought to be enough.
(setq recentf-max-saved-items 50)

(defun ido-recentf-open ()
  "Use `ido-completing-read' to \\[find-file] a recent file"
  (interactive)
  (if (find-file (ido-completing-read "Find recent file: " recentf-list))
      (message "Opening file...")
    (message "Aborting")))

;; get rid of `find-file-read-only' and replace it with something
;; more useful.
(global-set-key (kbd "C-x C-r") 'ido-recentf-open)

I can't take credit for all of this... I just borrowed pieces from other folks. Now C-x C-f uses ido to find files, C-x C-r uses ido to find recently opened files, C-x b uses ido to pick open buffers.

Edited to add:

Also, M-x uses ido to complete commands.