I know the OP said he was a VIM guy, but here's my first approximation to a random manual page script for emacs; it doesn't strip out directories (like man1) or specify different sections of the manual, but it indexes manual pages, so you not only won't try opening pages for commands that don't have them, but you'll get other pages too (eg, the TCL library man pages):

  ;; Taken from http://emacswiki.org/emacs/ElispCookbook#toc57
  (defun directory-dirs (dir)
    "Find all directories in DIR."
    (unless (file-directory-p dir)
      (error "Not a directory `%s'" dir))
    (let ((dir (directory-file-name dir))
          (dirs '())
          (files (directory-files dir nil nil t)))
      (dolist (file files)
        (unless (member file '("." ".."))
          (let ((file (concat dir "/" file)))
            (when (file-directory-p file)
              (setq dirs (append (cons file
                                       (directory-dirs file))
                                 dirs))))))
      dirs))

  ;; Taken from
  ;; http://stackoverflow.com/questions/3815467/stripping-duplicate-elements-in-a-list-of-strings-in-elisp
  (defun strip-duplicates (list)
    (let ((new-list nil))
      (while list
        (when (and (car list) (not (member (car list) new-list)))
          (setq new-list (cons (car list) new-list)))
        (setq list (cdr list)))
      (nreverse new-list)))

  ;; Display a random manual page
  (defun open-random-man-page ()
    (interactive)
    ;; Get manual page paths from the environment.
    (setq man-paths (parse-colon-path (getenv "MANPATH")))
    (setq man-dirs ())
    (dolist (man-path man-paths)
      (setq man-dirs (append man-dirs (directory-dirs man-path))))

    ;; Get a list of files in manual page paths.
    (setq files ())
    (dolist (man-dir man-dirs)
      (setq files (append files (directory-files man-dir nil "^[^\.].*"))))

    ;; Fixup the files to be a list of man pages.
    (setq man-pages ())
    (dolist (file files)
      (setq man-pages (cons (car (split-string file "\\." t)) man-pages)))

    (setq man-pages (strip-duplicates man-pages))

    (random t)
    (man (nth (random (length man-pages)) man-pages)))

Be aware that Emacs lisp is still something I'm learning; I'm sure the above could be improved.