Die Frage ist, ob du die Priorität auf leicht zu leiten setzt, oder Flavor eines bestimmten Hintergrunds simulieren willst.
Würde ich mit Tabula Rasa eine D&D4-Sandbox-Kampagne beginnen, würde ich das so angehen:
1. Verschiedene Terrains bestimmen, für die du jeweils eine Random-Encounter-Tabelle haben willst. Z.B. City, Village, Plains, Hills, Woods, River, Sea, Mountains
2. Das Monster Manual von A bis Z durchgehen und jede Encountergroup einer oder mehrer Terrain-Tabellen zuordnen. (Ich würde das noch nach Level oder zumindest Tier sortieren, aber das willst du ja explizit nicht. => Weniger Arbeit.)
3. Das Spiel einfach beginnen und schauen welche Encounters sich ereignen. Wenn es in irgendeinem Encounter einen interessanten (und wahrscheinlich mächtigen) Gegner gibt, würde ich dem spontan einen Namen geben, im recht klischeehaft spielen und dann abhauen lassen, bevor er umgebracht wurde. So kriegt man wiederkehrende Gegner.
4. Ich würde die Encounter so anlegen, dass es nicht notwendigerweise zum Kampf kommt, sondern dass (je nach Gesinnung?) auch andere Formen der Interaktion möglich sind. Dank Encounter Groups für Elfen, Eladrin, Dragonborn, Menschen, usw. wird sich auch da früher oder später was ereignen. Wie oft die "Guten" auftauchen liegt einzig und allein daran, welche Ergebnisspannen du ihnen auf der Zufallstabelle zugestehst. Gefährichere Regionen können ja einen Zuschlag auf den Würfelwurf bekommen und damit die Wahrscheinlichkeit solcher Encounter veringern.
5. Evtl. kannst du die Zufallstabellen noch mit generischen Non-Combat-Encountern wie Händlern usw. erweitern. Obwohl es da auch gut wäre die mit einer Eskorte auszustatten und sie erst in Encounter zu verwandeln. Hexland ist schließlich gefährlich!
6. Du kannst fertige Kurzabenteuer wie Dungeon Delves ebenfalls auf der Karte der Region verteilen oder sie gar auf den Zufallstabellen unterbringen.
Je weniger Gedanken du dir vorher machst, desto weniger Arbeit hast du. Und falls du nach der ersten Session überlegst, was eigentlich der Grund war, dass X neben Y durch die Landschaft wandert, hast du schon ein paar tolle Hooks, denen die Spieler folgen können, falls sie Lust haben.