Jed pointed me to a hexcrawl method I wasn't aware of called "Wilderness Hexplore Revised". It's on Scribd [Insert rant about Scribd being crap here], so I couldn't read all of it or download it, but the preview was enough to test out the basic terrain generation portion. It actually seems geared towards being used during play, rather than as a prep method, so that is a plus. In fact, I was able to roll three dice (d20, d8, d12) simultaneously for each hex and speed up the process of map generation.
Pros: Fairly quick Hexes are logically related to previous hexes. Nice variety. Potential for lots of detail, depending on subtables used for feature details.
Cons: It's on Scribd.