As someone who mains warrior, I wholeheartedly support an instant or at least uninterruptible clemency, and no combo breaking when changing stances. Will it completely fix Paladins? Of course not, but it would sure make them a smoother overall experience to play.

Make the above changes, plus add some sort of way for them to increase raid dps by 3-5% and they'd probably be about right.