The sandbox is different. The world is in motion, so a random encounter demonstrated this motion. A random encounter shouldn't be a haphazard chart of monsters from the back of a book the DM rolls on to come up with a fight. It should be an unexpected thing that happens, tied in with the environment. This is where the traditional random monster chart comes in handy, but with some tweaks.
First, all the monsters on that chart are hand picked. I know where they live. They're part of the campaign region. My campaign region doesn't have orcs, so you won't find orcs on the chart. If it's close to civilization, the various bandits, cultists and other impeding groups are included. Don't forget the people.
Whenever the party encounters one of these groups, I either cross it off or put a check mark next to it. Kill enough angry bears around town and eventually you won't be fighting any more angry bears. The bandit groups only have so many people in them. There might be only one bugbear, and you just defeated it. That's part of the dynamism of the sandbox.
I make my chart in a spreadsheet so I can sort by CR and get an average when I'm done. I want my concentric circles out from civilization to get increasingly dangerous. So my local forest encounter chart (below) is dangerous for low level characters, but hopefully not lethal with an average CR3 (The default Pathfinder forest table has an average CR5). Head into the hills or forests farther from town and I'll probably have a chart around CR5. Head deep into the mountains and it might be CR 10. The ocean is naturally dangerous, with most encounters in the CR 7+ rating, although I suppose you could make it easier with some work.
Also don't forget animals. Understand your local ecosystem and try to include as many as possible, especially the giant kind. For Pathfinder, Tome of Horrors was a godsend for its huge number of animals, along with monstrous plants. The new D&D 5 Monster Manual has a satisfactory number of these.
Second, what are they doing? if you have an encounter, it doesn't necessarily mean you're having a showdown with a monster. It's not always Perception checks and Initiative rolls. What is the "monster" doing? They might be returning from a hunt (possibly injured), on their way to a hunt, looking for food (or victims), building a shelter, or even fighting another monster. They might even be dead. Who killed the bandits? Hmmmm. If alive, they might not want a fight.
One of my favorite encounters from my last campaign was two Rocs fighting over a shark one of them nabbed from the ocean. The Roc was randomly rolled, along with fighting another creature. To make it more interesting, all the party could hear from the cloudy skies was the fight, followed a moment later by a shark, plummeting to earth (roll scatter dice). The victor came down for his shark and the party fought it and won (surprisingly).
|From Telecanter's Receding Rules blog|
Third, maybe it's not a monster at all. my highest numbers on my chart (95-100 rolling percentile) is not a monster at all. It's a random thing. There are various charts people have made out there, but they're pretty easy to come up with. You find a medicinal plant, there's a hazard, the road is washed out, the path is somehow lost, or signs of a battle. Perhaps a party member gets sick or loses something, or they notice they're being followed. Look online for other peoples charts, along with your own ideas (I stole mine entirely, and can't remember from where, so I won't post it).
Should you roll this in advance? It's up to you, but if you use miniatures and need extra work learning about a monster because you're new at this, then maybe yes. I don't like in media res (in the middle of things) encounters in the game, with that goblin fighting that elf, perpetually stuck in time. However, this might be a conceit worthy of that.
How often should you roll? II like to do it once during the day and once at night. I'll roll a D6 and something happens on a 1 or 2. I'll often not roll if we're in the process of doing something interesting, but when we're hex crawling, it might be the only possibility of action for miles.