Learn Russian: Я должен договориться с начальником. - I must come to an agreement with the boss.

While -ся often means doing something to yourself, it is also used for reciprocal actions. This means two or more people are doing an action with each other. Here, договориться means reaching a mutual agreement with someone else.

Why is начальник (boss) in the Instrumental case (начальником) here?

Reciprocal verbs like договориться are usually followed by the preposition с (meaning 'with') plus the Instrumental case to show who you are interacting with. So, начальник gets the masculine Instrumental ending -ом to become с начальником.

If I am a woman, how should I change the word должен?

You would say должна. The word должен (must/have to) acts like an adjective, which means it has to agree with the gender of the subject. Я должен means the speaker is male, and Я должна means the speaker is female.

Why is the verb договориться in its infinitive form here?

It follows должен. Just like in English where we say 'must do' instead of 'must doing', in Russian you use the word for obligation (должен) followed directly by the dictionary form (infinitive) of the verb.