I've run a sandbox game for the past couple years, a Pathfinder game of exploration of a long forgotten island. Pathfinder and D&D have high levels of magic, which means sandbox games tend to excel at low levels but run into difficulty at high levels as characters easily overcome physical challenges with spells.
My game limits certain types of magic as a conceit to the sandbox format. For example, teleportation magic has been nerfed thanks to a dispute amongst the gods. You can only teleport between standing stones you control, located on ley line conjunctions. Teleportation doesn't come into effect in this game until 9th level, so even if you don't do this, it leaves a lot of low to mid level play available.
My conceit limits teleportation to areas you control and encourages acquisition of nodes along this network. It also means once you've explored an area, you're not constantly hiking back and forth.
Flying is another sandbox foil. If characters can do an overland recon of your sandbox, there's not much reason to hike through it and explore. You can accept this, or like I've done, create flying hazards. First, my island is foggy and always overcast, like the real world island it's modeled after. Second, there are nasty flying predators that consider air space their territory, usually griffons and rocs, but there are a few dragons. Starting at 5th level, overland flight is going to be limited to the wizard, and the wizard doesn't need that kind of trouble.
So just a couple tweaks, really, to keep the sandbox alive. They're coming up on 12th level and it mostly works. Magic still overcomes challenges that were once skill checks, but it just means the nature of challenges need to change, but that has always been a feature of this game. Here are some capabilities characters gain by level:
Animals: Calm, Charm, Hide From, and Speak With Animals. Even the smallest animals become NPCs. Think about what they know and how they know it and their limits of understanding.
Healing: They have minor healing and suppression, but could be beset by disease, poison and other ailments. The Heal and Knowledge: Nature skills can be used to good effect to prevent and treat these problems. The Serpent Skull adventure path, book one, is a good resource. Use Environment to full effect.
Mobility: Druids can Pass Without Trace, but the others can't. Wizards can cast Mount but for a limited time. One or two characters better have Survival for tracking. A Ranger's favored terrain is likely to be very helpful, depending on the variety of environments.
Food & Water: It can be purified and extended, but not created. The Survival skill will be key at low levels.
Elements: Druids have Endure Elements against the heat or cold, but it's resource intensive at low level. Extreme temperatures should require Survival rolls to avoid the environment killing them.
Communication: PCs need to hike back and forth to deliver messages.
Animals: Hold Animal
Healing: Delay Poison helps, but herbs (Knowledge: Nature, Heal) can still be useful. Lesser Restoration solves many symptoms. The environment will remain a threat until 5th level.
Mobility: Wizards can cast Communal Mount for a good amount of time, so assume everyone is mounted. Levitate comes into play. Druids got Trackless Step at 2nd and now have Woodland Stride. Spider Climb can get past obstacles.
Food & Water: This will remain an issue, but their Survival ranks will continue to rise, making it easier. At 5th level Create Food and Water makes this irrelevant.
Elements: Communal Endure Elements makes weather temperature issues moot. You'll probably just stop checking for this. Rope Trick will eventually provide shelter for the night, but for now is limited to a few hours, like when animals attack.
Communications: Animal Messenger delivers messages as fast as the small animal can travel. Whispering Wind is good for a few miles.
Animals: Dominate Animal: nasty predators are now their best friends. Speak with Plants means even those can be a resource or tell a story.
Healing: Poison (for druids) and Disease are banished.
Mobility:Fly is in play. Communal Spider Climb. Lily Pad Stride and Water Walk means they can even walk on water. Phantom Steed improved on Mount. Water Breathing for underwater encounters.
Food & Water: Create Food and Water in play, so I ignore it at this point.
Elements: Campfire Wall plays a role in protecting camps from attack. Rope Trick is up to 5 hours now. Survival, as a skill, is beginning to shine.
Healing: Clerics get Neutralize Poison. Restoration.
Mobility: Phantom Chariot, Communal Phantom Steed. Ride the Waves and Communal Water Walk for full aquatic mobility. Air Walk for clerics and druids. Dimension Door.
Food & Water: -
Elements: Secure Shelter means they get a time out at night.
Animals: Commune with Nature to check out what's ahead.
Mobility: Teleport, Plane Shift, Communal Air Walk, Tree Stride, Overland Flight.
Food & Water: -
After 9th level, most sandbox challenges are no longer about wilderness survival or overland travel. These things happen, but it's now about the destination.