Half the party is lawful good, half chaotic neutral.
How did this party even form in the first place? Do they have any common objective? Do they have any prior relationship that ties them together despite their differences? I bring this up because I used to DM with a very light hand on character creation - just show up with something to play - and I got tired of the inevitability of this going bad in predictable ways as well as the forced nature of having PC's working together despite all rational and reasonableness suggesting that these persons who don't like each other, don't agree with each other, and are working cross purposes would never hang out together in the first place. (Unless, he's your brother, in which case, what are you going to do?)
To avoid a fight, and keep things calm, the LG Cleric offered a band of five evil brigands, who had clearly just done some horrible things, 'treasure'...
Wait... why? Why is the LG cleric dispensing with justice, offering bribes, and making deals with evil doers who show no signs of repentance? Did they beg for mercy? If so, why now do they get a share of treasure? What possible legal claim could they make on it, and what legal claim did the cleric have to give it away if it was stolen goods? What about the victims of the brigands? How will the LG cleric answer them when they cry out for justice? What about the lawful authority of the land? How will the cleric answer him when he asks whether the cleric is obeying and upholding the law?
Why in the heck did the Paladin go along with this? Isn't he sworn to bring evil doers to justice? I mean, the best he can do is swear they'll receive a fair trial. He can't make deals that violate the law to get something he wants, and he can't allow others to do so.
The behavior of the lawful good group thus far is more like Neutral or Chaotic Neutral. In brief, the logic of the characters is Utilitarian, Pragmatic, and Self-Interested. The brigands are obstacles in the way of accomplishing what they want to do, but are otherwise unimportant. Their stolen goods aren't stolen goods to be returned to the persons who rightfully own them, but 'treasure' to be claimed which they can distribute as they see fit.
Now, what about the 'CN' group.
they've now done that, and the CN bard whispers, ok, let's kill these horrible men.
Ok, so that isn't merely pragmatic. That's treacherous. You've just entered into an agreement with this group, and now you are going to backstab them. You have deceived them, and now having successfully deceived them you are going to take advantage of them. If they had an objection to the deal, they should have voiced it ahead of time.
That behavior is not Chaotic Neutral. That's Chaotic Evil.
The paladin, monk and cleric are in a very tough bind.
Well, duh. They acted like a bunch of Chaotic Neutrals and are in the habit of associating with evil backstabbing persons. It's a bind all of their own making.
The LG characters were saying a deal is a deal, but let's tell them they have to go into this certain room, we'll lock it up and go. the CN characters think it's crazy.
Well, the CN characters are right in a sense. This is crazy. Ok, first, the LG characters can't go back on their word. Even if what they just promised was unwise, they can't go back on it now. Even if they didn't have the right to do so, they can't just back out. If they break their word and are faithless (and IMO, they are faithless regardless of how they act now) because a lawful authority points out they didn't have the right to enter into this agreement, then at best they lose class abilities until they atone for their rash act.
But now the solution that they are proposing is to act faithlessly immediately, lock them up and possibly leave them to starve and die?!?!? Depending on the motives, that is either lawful or chaotic but regardless that's Evil. The supposedly LG characters made a deal in bad faith and now intend to act cruelly and vindictively. That's just evil. If they justify that by the fact that by the letter of the agreement they didn't say they wouldn't lock up or otherwise mistreat the brigands, that's lawful evil - devils make similar sorts of agreements, not paladins. If they go through it because now that they think about it they are willing to go against their agreement because they actually hate the brigands because they killed a friend, that's chaotic evil. If they entered into the agreement merely because they knew that they wouldn't keep their word anyway, the brigands would be forced to defend themselves, and then they could kill them only after having sadistically manipulated and deceived them (what you call 'properly slay them'), that's neutral evil. Regardless, if they go through with it, immediate loss of clerical powers and paladin class powers. I'd have to seriously consider this willful, you are now permanently a bad fighter.
LG can be so difficult to play...
To be perfectly frank, no it isn't. I have met many people who are incapable of playing anything other than LG no matter what they put on their character sheet, simply because their instincts for fairness, mercy, justice, and honesty are so strong that in play they can animate anyone that doesn't act according to those instincts.
In my experience, about 80% of players are only able to play a single alignment. I'm not sure entirely why this is, and I think there are at least two equally valid explanations, but that is what I've observed. In general, in play, CE is a very common alignment, and your party all seems to lean that way. This happens I think because in real life, personal self-interest is a major influence for most people, and because perhaps even more commonly since this is a game people tend to treat it primarily as something to win at any cost without seriously contemplating the moral aspect (interestingly, people under age 13 or so rarely play or act as CE characters, possibly because they take the play far more seriously or possibly because kids really are more innocent.) D&D in particular, by leaning toward 'Kick down the doors, kill the monsters, and take their stuff', seems to breed a 'murder hobo' attitude to the game particularly in groups that don't do much reflecting when they move from a more dungeon based play to supporting something more like a story.