When that wasn't successful, I switched to the command-line and used the nmh tools directly. No issues. Back to Emacs, I created a new message and noticed something: MH-E was trying to add X-Face/Face data, the image icons that get displayed next to your "From:" header. This was interesting, because I didn't recall creating a ~/.face file anytime in the past. Poking around revealed that Gnome had added my login icon as a ~/.face file! MH-E was dilligently trying to do what it thought was the right thing, and included it in each email I sent. I'm not sure why the process took so long, other than the image used was HUGE. Silly rabbit!
So, the following line in my ~/.emacs file guaranteed it didn't try this again:
(setq mh-x-face-file nil)
If I ever need to start including an X-Face or Face header, I'll update that with the appropriate path.
The second issue I ran into was found while trying to research the answer to this first one, the `dir' file for info wasn't being displayed from `emacs' when it worked perfectly well from the `info' command-line application. I uncovered this bug, and did a quick test. I decompressed the /usr/share/info/dir.gz file. It worked! (I also took the opportunity to edit the file and use English instead of German for the introduction. Not sure how that happened.)
In comparison between Debian Wheezy's version of Emacs and info file integration (emacs23) v.s. the Homebrew install I have running on my MacBook at work (emacs24), I'd have to say that the Homebrew install is winning out here. I may have to make a local build to keep up, or pull in some backports.