It's got layers
Dishonored isn't about player freedom as much as creating the illusion that there are endless ways to complete any goal—and that illusion is carried out with aplomb. Each of its nine missions is set in a tight-packed and detailed miniature sandbox, populated with NPCs, plague-infected zombies, soldiers and violent religious zealots, elite "tallboys" on mechanical stilts, dogs, swarms of rats, all manner of trap and defense, and massive amounts of loot.
The illusion is crafted within the layers of each individual objective and goal. For example: there may be a few ways to bypass a specific door. Use the key, break it down, or find an alternate route. That's the top layer. But where is the key? You can snatch it from a guard's belt. But it's also hanging on the wall in the gatehouse, and there's one hidden under someone's pillow in the barracks. And an NPC may give you a copy during a chance encounter in an alleyway.
What if you don't want to sneak around looking for the key? Then possess a rat and climb through a busted grate, or simply break the door down with a powerful gust of wind, if you've chosen to unlock one of those abilities. See where this is going?
The game's best mission takes place during an aristocratic masquerade party. Corvo finds an invitation (or he teleports over the wall, or he fights his way in). His goal is to eliminate one of the three noblewomen hosting the party (they're sisters), but first he must discover which one has been in bed with the enemy. Then he has to discover which sister is which (they're wearing masks, remember?). Then he can decide how to dispose of her—slit her throat in front of all her guests, lure her to the storeroom and dispose of her quietly, or find some less violent method?
You could map those choices out with sticky notes, sure, but in practice they make you feel like you've got all the freedom in the world—and that's a beautiful thing.