I would say that in an 'improv' method such as yours (which I have used in the past), is going to be a shallow pond. Working off the cuff, improvising as you go, you can certainly come up with memorable gaming; it can even allow for some player agency.
But for real, dynamic player agency, I believe that you need more detail and depth of plot than a GM can come up with 'on the fly'.
This is an empirical claim. I've never seen any evidence to suggest that it is true.
Here's a link to an actual play report of a Wuthering Heights one-off. As you can read, nothing was planned (beyond what is implicit in playing a game set in Victorian-era Britain): the players rolled up their PCs, including their "problems"; on the basis of that we established an initial situation that made sense (the mute monk PC had turned up at the bookshop where the politically radical and occult-obsessed PC worked); I (as GM) elaborated on that scene; and then we followed the logic of play.
We had fisticuffs, a political meeting that degenerated into a fracas, hearts smitten and broken, a body dumped in the Thames, a prison riot and escape, a middle-aged policeman brought to the side of radical politics, ghostly possession, and in the end the bookshop burned down by the PC who worked there, with himself inside it.
I wouldn't pretend it's great literature, but equally I wouldn't describe it as a particularly "shallow pond" compared to a comparable prepared scenario (say a Cthulhu by Gaslight one-shot). If the players have genuine agency - that is, are able to make action declarations where the consequences of resolution
actually stick and are followed through - then (i) the GM doesn't need to "come up with" a plot either in advance or on the fly, as the play of the game will do that, and (ii) there will be plenty of detail and depth.
How the content comes about it not the important bit. Meaningful choice and agency happen when player choices make a difference in what happens.
So, let's say the PCs are traveling long distance cross-country, and you imagined beforehand that a tribe of orcs was in the way. If the PCs negotiate with giant eagles to fly them over much of the intervening territory, but they then have to fight the orcs as soon as they land anyway, then you have rendered the choice to negotiate with the birds meaningless, and thus removed some of the player's agency.
If the players can make their own lives better (or worse) through their choices, they have agency.
I don't think that "better" or "worse" is the right metric here. When playing Cthulhu Dark, for instance, we know in advance that the PCs' lives will probably get worse (they will have horrible experiences and lose their grip on sanity). But that doesn't stop the players exercising agency in Cthulhu Dark play.
What is key is
do the actions the players declare, and the resolution of those actions, actually matter? Because
what matters is highly context-sensitive, so is player agency.
For instance, in your example, what is at stake in the players' successful recruitment (via their PCs) of the eagles as a player-side resource? If the goal is to avoid encounters, then the GM who allows the players to believe that they have succeeded, and then springs the orc encounter on them anyway, is negating or disregarding player agency. If the goal is to avoid the exhaustion of travel, then the GM who springs the orc encounter is probably not negating agency: the players get the benefit (be that mechanical, or fictional positioning, depending on system) of confronting the orcs unexhausted.
This illustrates why a useful tool for helping to preserve or enhance player agency is to understand what the players hope they will achieve on a successful check. Eg if it is clear to everyone at the table that the goal of the eagle gambit is to avoid encounters, and the players succeed on the relevant check(s), then it will be crystal-clear what the GM is doing when s/he nevertheless springs the orc encounter. (I think this relates to
@Ovinomancer's comments upthread about techniques that avoid illusionism.)
If you want to ensure that players are seeing the story-direction when it comes to mechanical points, you can make it very clear by use of the "If you fail, you get..."
While this can mitigate some of the surprise, it can also increase the tension of a die-roll.
This is the canonical procedure in Burning Wheel (as you, aramis erak, already know). Luke Crane admits in his commentary (in the Adventure Burner/Codex) that he doesn't always follow it. I'm the same when I GM BW.
But I think the idea of
clear stakes - be they express or implicit in the situation - is pretty important. Umbran's eagles example, and the various ways of cashing that out, shows why.
If the players don't know what is at stake (eg choosing a T-intersection with no knowledge of what is one way or another), then - in my own view - it doesn't increase their agency because the GM is narrating consequences based on pre-planning (eg a dungeon map and key) rather than making stuff up on the spot.
There are additional (sometimes unstated) GM-side conventions, beyond just preparing a map and key and sticking to it, that govern the design and adjudication of traditional dungeons that allow these temporary moments of low-agency to be the prelude to moments of high-agency (see eg Gygax's discussion of Successful Adventures in the closing pre-Appendix pages of his PHB). Roughly speaking, the more the game involves a "living, breathing, realistic" world the less those conventions will be observed, and hence the less agency the players can generate out of initial low-agency situations where they simply discover what the GM has prepared.
Hence, for player agency-oriented RPGing which wants to deal with rich, verisimilitudinous characters and settings, the appeal of non-map-and-key based approaches like PbtA, Burning Wheel, BitD, etc. That's not to say that these games are, or have to be, prep free; but the role of prep is pretty different from what it is in traditional D&D. Most importantly, prep rarely provides a basis for declaring - by reference to fiction known only to the GM - that an action declaration fails. That's key to how these approaches maintain player agency by not obscuring the stakes in action resolution.