Typically, something like Fate's phase trio: https://fate-srd.com/fate-core/phase-trio . The tldr is you establish history between the characters before you start.

I don't really like the "you are working together because you're both players at the table, not for any in-character reason" trope at all.

The example you give in your OP is not a good idea for an interactive storytelling game with friends. It has too many spots where the players might want to do something, and you're going to want to reject it because you have a set idea of what needs to happen. Either take this idea and move it to your "I should write a book" folder, or start the game where it has already happened.

You can totally start a first session with "You were hired by Dmitry Peacile to do a job. The whole time he was aloof, arrogant, and insisted things be done his way while you stay out of the way. It became apparent you were only there for a technical reason in the contract, even though he kept the paper on his person and never let you read it.

Well, just a few minutes ago he rode his horse over a rickety rope bridge while insisting you all wait here. The bridge gave way, Dmitry, his horse, and the contract that entitles you all to a big payout plummeted into the depths of Goblin Song Gorge below.

What do you do?"

Now you're starting where the players have some agency instead of possibly wasting hours doing stuff where you don't want the characters to change things.