Just as a side remark, but in parser-based games, it’s usually not “random guessing”. If the game is well-designed and well-implemented, then the player will be able to form a decent idea of what he is supposed to accomplish next, and how to phrase it.
(ATTACK GOBLIN or TALK TO GOBLIN or even just TAKE PURSE might be reasonable things to try, for example. Or just GO NORTH and venture forth without the gold.)
But, to address the question of giving the players the feeling of agency in a choice-based game; here are some ways of doing so, for example:
You can have more than two choices. You shouldn’t overwhelm the players, but nothing’s stopping you from providing three choices per node (on average).
(Of course, you need to take care to join some of the strands together again, otherwise it would become impossible to handle the exponential writing workload.)
That should at least help to alleviate the impression of being funneled through a narrow set of possibilies.
You can make the choices have meaningful consequences (and make that clear to the player – there was a related thread here recently: How do you "show" choice in choice-based IF?).
In your example, maybe the choice to attack the goblin has the outcome that the whole goblin tribe is hostile to you now, or raids your village in revenge. Whereas the choice to talk to the goblin might lead to a peaceful resolution, and later you can enlist the tribe’s help against a dragon.
Sure, those are two paths which the author individually predetermined for the players, but still, the fact that the choices matter will help with the feeling of agency.
And if you implement several more of such choices, then the players will (justifiably) feel that they are shaping their fate within the story.
Another way, but of course not mutually exclusive with the others, would be to include a more “systems”-like approach, as RPGs and RPG-like games often do.
You can implement stats/attributes, and an inventory, and places which the player can revisit, where you open up more options on later visits, depending on whether the player has enough wisdom / gold / faction reputation / experience points and so on.
In your example, you could offer choices depending on the player’s stats, for example: steal back the purse (high dexterity required), intimidate the goblin (high strength or charisma), explain the concept of justice (high wisdom), and so on.
Or, if the player has the “animal summoning” skill, he might summon a thieving magpie bird and order it to steal the gold back from the goblin.
This will typically give players the feeling of really inhabiting that world, and it will also lead to such a vast range of possible paths that they won’t get the impression “I’m just choosing one of the two paths which the author set up for me”.