Down a rabbit hole we go...
So, if my players go off in some random direction without asking me about it then that choice was not informed and thus they lack agency because I could just make up whatever and they wouldn't know any better. Sounds fair.
However, if they ask me to provide details about where they might go and I give them info about it, then they have agency because they are informed about the possible consequences of going there. Sounds fair, as long as the info I gave them is correct.
So, there's a pretty big pea being hidden under this mattress, and that's the assumption that the player choice is uniformed. This almost never happens -- players are making a choice to go in a "random" direction not because they are actually random but usually because there's some other motive at play. Perhaps they don't like what's otherwise available, so the choice is on to not choose any of what's already up. Or, they're engaged in some level of metaplay where they think their thwarting a GM plan they don't want, or, maybe they are random. In each of these cases, though, the players are exerting their agency.
The kind of uninformed choice that's problematic isn't one where players make a choice without perfect information, but rather when the GM offers the players a choice without sufficient information. A T-intersection in a dungeon passage, for instance, is an uninformed choice if the GM hasn't provided any information about what on either path. Provided the GM has prepped the dungeon, the choice can matter, but it's a coin flip at the time of the choice. This doesn't engage agency because they players aren't actually making a choice, they're selecting a random outcome. If the GM does provide information, though, perhaps in foreshadowing or prior fiction (like a map), then this choice is fully engaged in agency.
Illusionism happens when the GM offers such a choice but both passages lead to the same thing -- and becomes worse if there's additional information that appears to make the choice an informed one.
Uniformed choices are about what information is available before or during the choice. Illusionism is about a forced outcome making the choice irrelevant.
What if the info I give them comes from an in game source, such as an NPC, then later I decide that the NPC was lying and the info they got was wrong. Then I could make up whatever and they wouldn't know any better, but then does that mean they lack agency because of the fact that they made an informed choice based on an in game lie?
This is engaging in Illusionism, and is denying agency. It's an interesting subvariant of Illusionism, because the decision to create the illusion of choice is after the fact. By deciding after the fact that the NPC is lying, you've negated any choices made during the encounter with the NPC and forced a specific outcome. The most important thing to do in either prepped or improved play is to honor established fiction. Do not introduce a change to established fiction unless it makes sense as a direct outcome of current play. In other words, you deciding as the GM that the NPC was lying is removing agency. The players discovering that the NPC had lied because they've suffered a failure on an important task that relied on the NPC's statement can work, though. Here, the NPC's truthfulness is a trusted fact, but the PCs have failed their task due to a bad roll or poor approach, then discovering that the reason their attempt failed was bad info can be a reasonable play. I'd be careful about using this, though, unless you're table is strongly rooted in play that directly challenges PC beliefs. It can result in bad feelings. I usually find it better to not engage in such things, as I'd rather my players not develop paranoid tendencies -- they're not fun for me.