As the others have said, this is an excellent problem to have as many people start too far the other and it's much harder to train them out of that!
Some simple examples:
Have an orc agree to let them pass, go gather up his mates and then attack them from behind while they are talking with the next group of orcs. (Obviously stat the encounter so it is still manageable.
Just have them attack, either ignoring diplomacy completely or having no common ground. "You on Ughs land. Ugh eat you now!".
As already mentioned show ahead of time that these things are evil. They may talk their way past this monster - but it's just eaten a whole family, are you going to leave it alive to continue doing more of the same?
Non-sentient enemies can't be negotiated with.
Now some more complex examples:
"You want to pass, what's in it for me?"
You could charge gold, you can have them see a necklace that is high sentimental value for one of the characters and decide they want that, you could make them do a side quest.
"Urg like shiny things! Give shiny thing you go." - Ugh points at the pendant your great aunt Edna gave you on her deathbed.
For the side quests prep a couple of side quests with multiple and vague lead ins. You can then re-use the side quest for multiple encounters until the players bite on one and decide to do it. For example:
An ancient temple of evil is overrun by snakes - prep the side quest. Now your encounters:
A paladin wants you to destroy the temple
An evil cleric wants you to clear out the snakes
A druid wants you to break the curse holding the snakes in place.
Even if they turn down the evil cleric, they still run into the paladin so your side quest still has a good chance to get used, just with a different hook into it.