Another article from Fight On!, this time from issue #11, is "Handy Tables for Hexcrawling", by Alexey "Monk" Fotinakes. His intention is actually much closer to what we're looking for: creating new terrain during play as characters explore the wilderness. This is the only hexcrawl procedure I've seen to incorporate multiple levels of detail, in this case based on speed and thoroughness of search: there are three tables for three levels of detail (general terrain, special feature, and landmark.) The GM consults a table for speed of travel and rolls to see how much detail the explorers discover in each hex. This means that PCs rushing to get somewhere only discover general terrain, while rolls for greater detail can be skipped until the players actually decide to explore the hex more thoroughly.
The features and landmarks, on the other hand, are quite varied. Many of the results may have to be changed for specific campaigns; the mix seems to be geared towards science fantasy/post-apocalyptic wastelands with a touch of magic, somewhere between Thundarr the Barbarian and Planet of the Apes. However, the items described aren't dull, but cry out "Look at me! Touch me! You know you want to!"
Pros: Quick and simple when used on the fly. Level of detail varies with player action (skip some rolls when not needed.)
Cons: No mountains, sea, or some other terrain. Adjacent hexes not logically connected.