I do think that danger level should be communicated to the PCs in a Sandbox style game. Do this both in game and out of game. Out of game tell players: "Just because you can get there and just becuase you meet something doesnt mean you can beat it. Learn other ways of dealing with challanges early. On the otherhand just because you run into a band of kobolds at 10th level don't expect them to be a challange or to get any XP for killing them."
This should encourage players to do a couple of things. First is to plan on a variety of ways to meet challanges. That means those ranks in bluff, diplomacy, and sense motive aren't going to go to waste and enchantment spells are very useful. It encourages them to think creatively and pay attention to the world around them.
In game there should be multiple ways for smart players/PCs to realize that something is going to be to much of a challange, or not enought of one, for them. Let them hear rumors or reports from different areas, make Knowledge (X) checks for them and tell them what their PCs know about a particular thing, or have physical signs that they can observe that allow them to judge the nature of the kinds of threats they will face in an area (a giant foot print, the signs of dragon breat weapons being used, or an obviously kobold made spear left in a looted farm house). You should also make it possible for them to deal with encounters in ways that dont require fighting. Either allow them an opportunity to retreat or make some other plan. IOW don't say "You see a giant, roll iniative." That tells the players that the giant is going to attack them. Maybe he wont. Maybe he is asleep, maybe he is hurt and if the cleric heals him he will go away and leave the village alone, maybe he is looking for soemthing and the PCs can get it for him, etc. Give them the opportunity to deal with higher EL events in creative ways. The same applies for those challanges that are too easy. Personally I think that its good for PCs to occasionally wipe the floor with an opponent. Show they are the powerful butt-kicking heroes they want to be. But repeatatvie encounters would get dull quickly. Handwave them, and dont give out XP or significant loot, or make them an opportunity for something else to happen. Maybe the band of kobolds have a sorcerer who can detect magic at will. He sees the PCs and realizes that his clan is outmatched - they surrender to the great and powerful ones and beg them to spare their lives. They agree to give them all their treasure, which just happens to have been stolen from them by an evil Troll Blackguard. Or they start worshipping the sorcerer PC and become equal parts help and hinderance as they go into town shouting that all should bow low before the dragonblooded god that walks the earth.
Don't change the CR of things just becuase the PCs level up, or at least don't do it always. The bandit king that would have been an appropriate 3rd level encounter is going to be gaining levels of his own if the PCs don't deal with him - it makes sense in game because in a way he is an adventurer too. Having an isolated band of goblins doing that doesnt. Do give the players a chance to have a creative and fun encounter whereevr they go. Don't be afraid to kill PCs when they do something stupid. Do warn them off, in game and out of game, when they are wasting their time in the valley of the 1st level commoner kobolds.