There are thee kinds of sandbox, IMO:
1) Open situations/locales: A megadungeon, for example, is not a crawl through the overland, but if its designed to be open - to have many points of entry/egress, many level connections, players can come and go to most places in any order they want, etc. - then I'd consider it a sandbox. I don't mean to imply that all non-linear dungeons are considered sandboxes, but if the party has the run of the place on their own terms, then it's probably safe to call it a sandbox.
2) Hex crawls: You take a map of an area, you lay a hex over it, then you essentially erase the map. Player's say "what's beyond the forest to the north?", and they go to the hex north of the forest hex to find out. It's more for exploring an entire realm - every river, every canyon, every thicket or glen. It takes way more prep because you need to fill a ton of hexes (usually). I view it like walking around a dungeon checking out rooms, except the rooms are all hex shaped, have no walls or ceiling, and are several miles in size. Instead of "three orcs guarding a chest while playing cards", hexcrawl "rooms" are more like "orc village gearing up to do war against the goblin village SW" or whatever. A dungeon where everything is on a grander scale.
3) Points of light: A scattering of destinations, where what many people consider the "boring" parts of a hex crawl are generally omitted or condensed. If you explore a desert in a hex crawl, you wander aimlessly making a path through the hexes, looking for something. You encounter stuff along the way, and you usually have a goal to find, but you don't have a specific destination to get to most of the time. If you explore a desert in a point of light campaign, it's because you are on your way to something you already know is in/beyond the desert. You don't need to "crawl" around and search for something (hence the "crawl" in "hexcrawl"). You go to the Temple of Sleeping Sand Bears or whatever, and on the way you face desert-themed encounters.
I suppose you could argue that story games are like sandboxes too, but we don't talk about those games around here.