Understand what Player Agency is
This is my definition:
Players making informed meaningful decisions that have reasonable consequences that can be foreseen
To have agency in the first place there must be:
- a decision of consequence to be made. A T-intersection in a dungeon with no other information is not a decision of consequence and no agency is available or needed. If it has signpost with one arm saying "Ogres" and the other saying "Gnolls"; then there is agency involved.
- enough information to determine the options that are available to them. One of which might (should) be the option of acquiring more information or determining the veracity of the information they have: are you really going to believe a signpost you see in a dungeon?
- enough information to determine the likely outcome of those options. A party of total newbs who draws their information about ogres from Shrek and thinks a gnoll is something JFK wasn't shot from does not have enough information.
- a willingness, on the GM's part to deal with the fact that player agency always, ALWAYS f*&ks up your plans. This is because there is always some pain in the ass wizard who will use Passwall to make the T-intersection into an X-intersection.
The problem you have is that you have tried to allow agency in a situation where the needs of the game require that there shouldn't be any. The player characters have to meet and form a party in order for the players to have any fun. There is no question of allowing in-game agency here - the players have already executed their agency out-of-game by deciding to play the game together in the first place. The only options here are follow the thief and play the game or do anything else (Sleep spell anyone?) and don't play the game.
There is a sin worse than denying a player agency: its pretending they have some when they don't - this is called illusionism. For whole bags of discussion on this see:
I know I'm not supposed to take away player agency or narrate their actions for them
I hope you now see that sometimes its not appropriate to give player's agency. Notwithstanding, I agree that you shouldn't narrate their actions; so don't paint yourself into a corner where you have to. Its perfectly acceptable to narrate the outcome of their actions:
Player: We've decided we want to explore the Tomb of Horrors because we are tired of life.
DM: OK, after several months of researching its location and several more months of arduous travel you are standing at the base of the hill in which it is reputed to lie.
Why did we do this? Because research is no fun, arduous travel is no fun, dying in the Tomb of Horrors is where the fun is and we play games to have fun. Have you denied agency? No, because the decision had been made - this is just the consequence of the decision. If your players feel you are trampling on their agency rely on them to say "Wait a minute! I wanted to X, Y and Z before we got here." You can then decide to say "OK, you did X, Y & Z" or "OK, you did X & Z tell me how you were going to do Y".
Don't equate railroad with bad
Every game is a railroad to some degree.
The player's can only play in the setting I offer. They can only play the game I offer: "No, you can't use your Shadowrun character in my D&D campaign". They can only play using the mechanics that the game system allows. They can only play when I hold sessions. They can only adventure in the sites that I decide exist and interact with the NPCs that I decide are there and who react in the way that I decide they do.
Sure, all of these are big ticket things but they all put constraints on player agency. Furthermore, everyone accepts that these are reasonable constraints within the context of the game.
At a lower level, if you join a campaign that I tell you is based on the Tyranny of Dragons adventure path then you have agreed that you will follow the railroad that is that adventure path. Within that constraint I will do my best to give you all the agency you want but if you decide that you will not move from adventure train stop 1 to adventure train stop 2 then the whole campaign is coming to a shuddering halt because I don't have anything else to offer you.
Even if I offer you a sandbox campaign then you can only adventure in the places where I put the adventure sites. You can even think of a sandbox as a railroad network: sure its not a single line going from A to B to C to D but if A, B, C & D is all that's out there then the only difference between the sandbox and the railroad is which train line you ride first.
As an aside, the sandbox only provides agency if the players know about A, B, C & D and know what the difference between them is. The point here is that you can have a railroad that enables agency and equally you can have a sandbox that denies it. There is noting inherently good or bad about either structure.
How to avoid it
Don't get wedded to a story. Stories emerge from playing the game; in preparing a game focus on situations and motivations of the NPCs and the PCs. Decide what happens next based on what happened before rather than having some pre-conceived idea. Take a look at Don't prep plots for an explanation of what I mean.
As to specifically forming a party, this is not an area where agency is a good thing. The players have agreed to play ergo they must play together: deal with this as a fact. Why the character's are together can be handwaved or backstoried or played out in a boring and insipid fashion because given that everyone knows the characters will form a party there's no source of dramatic tension (no prizes for guessing what I think of this last option).
Within the context of D&D 5e there is no reason at all why other members of your party can't just be a bond or, perhaps more interestingly, a flaw.
Or you can steal ideas more widely, for example, I am thinking of stealing from Technoir (the player's guide is free and this stuff is on page 6) the idea of Connections. Give the players a list of PCs and NPCs with a one or two sentence description and allow them to choose a number of Connections equal to say 3 + Charisma modifier. For example:
- Adrienne Chao (NPC): The heiress to the Malachite fortune.
- January Jade (NPC): A smuggler and weapons dealer who gets dwarf forged steel into orcish hands.
- Arma Winn (PC): A wannabe wizard whose master just died.
And my PC might choose: Adriene (lustful), January (antagonistic), Arma (respectful). How these connections get fleshed out (if at all) will emerge in play.