My answer is much simpler than the others. In my past gaming experience, I've seen players feel railroaded, and players that felt the world was incredibly open, and the biggest difference was this single overlookable thing:
How much detail the DM used for the world.
If you say:
You enter a room, and ahead of you, there's an Orc, who looks ready to attack.
Players will immediately sword the orc until it's dead, like they've done a million times in the past, and advance to the next room. Predictable, and incredibly boring.
However, if you say
The rogue, sneaking quietly, leads you into the doorway of a room 20 feet wide and 30 feet long with creaky wooden floors, scored grey stone brick walls, and at the top, about 10 feet up, a cavernous ceiling with stalactites, that appear slightly slimy. There are wide cracks in the floorboards, and below them appears to be roughly worked stone, probably mined out by cobolds. The boards appear only barely able to support your weight, due to rot. The walls appear to have been added later, in 1ft by 2ft bricks of an oddly marble-looking stone, which is cold to the touch. The walls appear well made, you suspect humans had moved in after the cobolds and attempted to make this into a home, ages ago. The warm moist air, and the rot and mold reveals that there must be an underground lake farther back. Near the front of either wall appears an incess in the stone,lined with wood, as if someone attempted to put the sembalance of a window there. To the left of the back wall is a rotted doorframe, open to a dark path, that appears well traveled. On the wall with the doorway you're peeking through, there appears to be a simple cloth war banner hanging, which, though tattered, doesn't appear more than a few years old. There's a surprisingly stable wooden bench/table near the center of the room, on top of what appears to be a red rug. The rug appears to have had an image on it, but is worn away to illegibility. There appears to be strands of a fringe on the rug that is mostly missing now. There are three unlit lamps hanging in a square from the ceiling, and another on the floor toward the far door. The right wall is lined with tall empty bookshelves, though the four bookshelves on the far half of the room have toppled toward the middle, on top of a shattered chair, and what appears to be a bit of shattered pottery. The left side appears to have a mostly-solid looking counter made mostly of wood, with what appears to be a very skillfully made stone sink inset. The counter appears to be covered in dried blood, with a scattering of animal bones and gore. The drawers beneath the counter are mostly open, and there's a few pots and pans remaining. There's also a few shards from the remains of a mirror in the sink. In the back right corner is a bedframe, which appears to be filled with hay, and an orc quickly fumbles his way awake, and grabs a chair-leg and swings it menacingly. He is wearing well-made pants with a tear in each knee, and a simple cloth shirt, but a surprisingly well made brown vest. On his vest is a small golden badge in the shape of a coin. Near the bed is a nice red beret. He yells out in Orcish "This is my place! Get out of my place!"
I've described the floor, walls, and ceiling, each different. There's several large objects scattered throughout the floor, and at least one interesting object on each wall. The monster wasn't just waiting for random adventurers, he was interacting with the environment (the bed), and has a reason for being here (his home? A temporary camp? Who knows?). What he wears differs from other orcs (high quality pants, vest, and baret, though torn, and a badge).
Now will your adventurers use the table to assist in combat? Maybe they can use the lamps? Or the bookshelves! Maybe the bard wants to calm the poor orc, and learn why he's here. Maybe the Wizard has to think twice about fire spells, because the floor and props are all wood. Or maybe he doesn't, because it's all wet and rotting. Maybe electricity can be useful, with all that moisture. What does the orcs badge and beret signify? Do they recognize the badge? What about the war banner? What happened to the kobolds who were here long ago, and the humans not so long ago? The PCs will find creative ways to use every detail you provide, and if you provide enough details, they find a way to use them to solve anything that needs solving.
So, when the players get stuck, describe everything in detail. Then describe those things in detail. And keep them different, and make sure to add one "interesting/usable" aspect to everything. The jail bars have to have a red bar, made of a different metal that spins, and makes a noise. Maybe it's a way out. Maybe it's a way to send a signal. Maybe it's a way to irritate guards. Maybe it opens up a story with a prisoner who's been here longer. Have no idea where you're players will take you. Just reward all interesting ideas with more plot hooks, and the players will be out before the second daybreak.
I like to keep a random name/background generator tool handy, and each time they decide to interact with an NPC, take 30 seconds to study the generated background, and then proceed. Does this NPC have a family? What does he like to do in his free time? What's he most afraid of? Is he a tattletale? Does he have a child he's kind of afraid of because he doesn't know how to be a good dad?
Maybe he likes cats. Or bards. Again: The more details, the more interesting, and the more likely the PCs can find a way to use this NPC to solve their problem.