Looking over the comments on the true improv hexcrawl post makes me think I should do a sort of review of each of the random hex generation techniques I have a copy of. Three from Fight On!, one from the DMG, one from the Judges Guild ref sheets, one from Kellri, any others I can recall. Unfortunately, that won't include the game fireinthejungle mentioned, Sources of the Nile, which I've heard of but never owned or played.
But one of the ideas that occurred to me about how an improv hexcrawl should be approached is that you need to generate material of varying detail on several levels simultaneously.
There's a broad terrain and political level, which will be very sketchy ("There's a mountain range over there, a forest over there; the capitol of our kingdom is three weeks travel south, a rival kingdom is four weeks travel west, and dangerous unclaimed wilderness is to the north.")
There's a middle detail level at about the barony-wide scale (one-day's travel in any direction.) This ought to include any settlements the size of a hamlet, major roads and rivers, and individual mountains or foothills.
There's a more detailed level within a single hex (two leagues across.) This should include major visible landmarks or structures, small paths and streams, and anything that could prove an obstacle to travel.
And there's the most detailed, subhex level, which would only come into play when actively searching a hex or setting up an outdoor encounter area.
The first three need to be rolled and described simultaneously in some way.