My very first time as a GM, I showed up to the session with a great pile of notes and plot. Half an hour later I threw it out and started improvising because they'd gone in a totally different direction. Over the years most of my players have been willing to follow a railroad if I ask them to, but I've developed a totally different kind of session prep which makes it so I don't have to ask that:
Don't have a plot.
Instead, have a status quo, something which disrupts the status quo, and a reason that the disruption forces action.
This isn't the kind of pre-made adventure we usually see, because it's hard to generalise for a widely published product whose point is to minimise the pressure on the GM mid-session (other systems, like Fate Core, take an approach similar to mine for some of their published adventures). But for individual campaigns it can be very powerful.
This concept is predicated on the idea that the only thing you can count on a group of player characters to do is to be unexpected. Planned plots tend to fall apart at their touch.
I'll run through the process with a quick example, but keep in mind that it's going to be a lot more organic than I make it seem. In practice, I go back and forth between the steps as one part gives me new ideas for another.
What's the status quo?
I need a location, and its inhabitants. The scope is up to me--maybe just a small dungeon, maybe a town and a nearby cave, maybe a whole nation. Let's start small. The reason "dungeons" work so well is that they're contained and limited: the number of options (places to go, people to meet) is more controllable than in a sprawling open area where the players can choose to wander any which way.
Location
A small underground catacomb: crypts, inner chamber, secret chamber connected to both.
Notice that since I don't need to control what order the party does things in, I'm free to have the secret chamber connected to both of the other areas. This also increases opportunities for the party to find it, since I really want them to do that.
Now I establish who's living there: why they're there, what they want, and what they are doing to get what they want (intelligent recurring NPCs may also have secondary goals, and backup plans and contingencies!). I'm going to choose things that I think are cool. That way no matter what happens, cool stuff will be involved. I like Sealed Evil In A Can plots; the idea that kobolds worship dragons; and the notion that dragon magic is closely linked to their physicality. I also like setting up situations where it's equally reasonable for the players to conflict or cooperate with an NPC.
Inhabitants
The crypts are home to a small tribe of kobolds who worship and serve the dragonling that lives in the inner chamber. A malevolent spirit is trapped in the catacomb's inner chamber.
- The spirit is the ghost of a tyrannical king. He wants to break free and possess the most cunning person he can find. The major obstacle to the king's freedom is the dragonling. He's influencing the kobolds to be more violent and aggressive, to call attention to the catacomb and thus hopefully get rid of the dragon.
- The dragonling lives in the inner chamber to keep the spirit trapped. Her spells of binding are powerful, but fade quickly in her absence, so she has to remain in the catacomb. She doesn't want to spend her whole life like this, so she's planning an exorcism ritual which requires a holy relic from a nearby village temple.
- The kobolds worship the dragon and serve her, raiding nearby towns for food and valuables so she can concentrate on keeping the spirit entombed. They've just stolen a relic from a temple and (because of the ghost's influence) killed a priest.
So we've set the stage: the ghost and the dragonling have goals they're working towards, and the kobolds are their pawns.
What's disruptive to the status quo?
In most D&D adventures the most disruptive force you can possibly muster is the party of player characters. I've dropped plot hooks into my adventure: stolen religious relic, murderous kobolds, and the promise of treasure. That should be enough cues for any party to start sharpening their swords.
But more specifically, I've engineered the adventure for a specific kind of disruption: the tenuous balance between the ghost and the dragonling will be tipped one way or the other depending on what the party does, but it'll be very hard for them to not tip it at all.
What does this look like in terms of what I bring to the session?
I sketch out maps of the location and its major areas; make the stat blocks for kobolds, dragonling, and ghosts; find a few interesting terrain hazards to use; and sprinkle loot drops through the catacombs as needed (most of it is probably in the dragonling's inner chamber, with another single big piece in the secret chamber). I'll knit these mechanics together into encounters on the fly, as needed depending on the party's actions.
Now I don't have to anticipate what my players will do or try to force them into certain channels in order for plot to happen. If they set foot in the caves, I've got a delicate situation they'll disrupt and NPCs whose responses to the disruption I can improvise on the fly. The order they go through the crypts, and whether they find the secret chamber before they encounter the dragon, doesn't matter to my prep: I've created and statted a living environment rather than making canned encounters which require the players to follow an anticipated set of particular future actions.
This is a lot more work--at least until I got the hang of it--and it often means that parts of my environment don't get used so that preparation effort is wasted. That's sad. But in a prep-heavy system like 4e, this is the best way I've found to avoid railroading: create living environments with NPCs that have plans and goals they're working toward, and provide plenty of spots for the party to mess up their plans. It enables a lot more dynamism than coming up with a plot I need them to goosestep through.
Roll20 is not kind to this approach.
Because you have to input your work to the system ahead of time, it doubles the wasted effort of anything which doesn't get used. Additionally, whipping up an encounter on the fly is easy when you've got a handful of stat blocks and a wet-erase map, but it's a lot harder when you've got to put all of that together beforehand.
All I can suggest is that you use narrowly defined locations (like the catacombs) so you can put in the maps ahead of time, and drop all the stat blocks into every map so you have them available if you need them. I don't have enough experience with roll20 to give any more specific advice on that front, but I know that it may be a big enough obstacle that my answer could be next to useless for your particular situation.
What you might be able to do is create generic setpiece encounters which can be quickly re-fluffed to meet the narrative's current needs. I dunno how much Roll20 will support that, but it shouldn't be too insanely difficult; I've even made sets of generic monsters which I could drop into most any situation with a different name each time.
The essence of sandbox play is following where the players lead, and it sounds like you're already doing that.
What adding randomness does is make the world feel more alive and larger than the thread that the PCs are pursuing/creating, allowing the players to make informed decisions about where they want to drive the game. You don't need to be constantly interrupting them with random encounters, but using them as a "spice" enhances the game and increases the players' knowledge of their environment, which itself increases the players' agency.
And don't worry about diversions derailing the campaign or slowing its advancement—the point of a sandbox is that there is no right path. If your players choose to diverge from their goals… it's because they have more goals than the one. If they want to advance one goal (not "the campaign"), then they will prioritise that goal even when distractions occur.
As long as your randomly-added distractions aren't mini side-railroads that force the players onto them, you can trust that they won't interfere with the players' freedom to choose their direction and speed. If the players choose to be distracted: that is where the campaign is. If they choose to not be distracted: that is where the campaign is.
Just remember that the campaign is where the players lead, no matter whether it was their idea or yours, and you can cut through this Gordian knot of worry about whether you "should" distract them with random things and whether the campaign is advancing at the "right" speed. There is no right speed or direction in a sandbox, only choices and outcomes.
Best Answer
They're really not that different...
...because you left out an important adjective: abandoned.
Often, those "fantasy" adventure locations you cited - a crypt, a prison, a cave system, a necromancer's lair, or a castle - are only interesting because nobody is currently and legitimately/legally living there. They're full of loot because it's stuff that was left behind when whomever built the place departed. They're generally not being used for their original purpose.
For example, crypts are places the dead are buried. If those dead folks have families who are not equally dead, it's entirely likely that there's no loot and no monsters, because relatives keep their family's resting place neat, clean, and secure. A necromancer usually doesn't have a "lair" because he built it, but because he found it, and he only found it because somebody else left it behind.
If you want to have a similar looting type experience in a non-fantasy game, you have to use similar abandoned locations. To use another of your examples, an active prison in both fantasy and science-fiction games is going to be filled with prisoners and guards. It is going to have a logistics organization - deliveries of food, drink, medicine, and so on. In either setting, it's good for a stealth/infiltration kind of mission.
An abandoned prison is a different story. You have to ask yourself why is the place no longer in use? Somebody built it where they built it for a reason, filled it with prisoners, and employed a staff of guards. Why did they stop? Where are the prisoners? Where are the guards? If the guards are gone, but the prisoners are not, why?
In your case, the bigger difference in feel is not about the fantasy/sci-fi split, but the source of authority. For the most part, fantasy adventurers are independent contractors - they take the jobs ("quests") they want, and ignore the rest. When the characters are regularly working for an organization, their end goal is always making the boss happy - they're collecting a paycheck, not loot.
It swings back around to asking those "Why?" questions. The interesting elements come more from the roleplaying about the characters motivations than blowing the heck out of things. I'm not just talking about the player characters either. Why is their boss sending them on these missions? How does his boss feel about it? If they're government, what do the people of their country think about what they do? These are the elements that make a "highly sponsored" or "well funded" game tick. There are a plethora of non-combat scenes that you can get out of delving into the motivations of the involved parties.
And of course... none of those questions are science-fiction specific.
...when you know why your locations are even worth an adventurer's visit.