The first game I ever ran was in D&D 3.5. This is an account of the first session of that game.
The party was called to an audience with the king. He told them that one of the more far-flung regions was reporting a growing rebellion. Rather than start by sending the army, the king wanted to take a shot at using a less expensive set of adventurers. They were given papers that instructed the local governor to cooperate with them, as they were acting on behalf of the king (yes, that is an excessive amount of power to give a party in their first game; I was a new DM).
The party traveled a week or two to this distant region. On the way in I described the abject poverty in which the people were living, contrasted with the palatial mansion of the local governor. It was clear after talking to some people that the "rebellion" was basically Robin Hood and his Merry Men. I assumed that the party would follow one of two basic paths: they would complete their contract, leaving the populace to suffer, or they would join the rebellion and hope for the king's understanding.
When the party finally made it to speak with the governor, he began to paint himself the victim. The party politely listened to his side, took out their papers, and requested to see all of the governor's accounting records. After a few good rolls, they were provided with tax records, which they proceeded to audit. They then convinced the guards that the governor was committing tax fraud, and they arrested him. They even convinced the Robin Hood character to go back with them to testify at a trial before the king.
Who says that PCs always resort to violence?