You can definately tell that we don't have a lawful culture anymore.
Nifft and Mr. Fidget are correct. The Paladin doesn't lie, nor is he insulting (which would be just as bad). The Paladin is tactful. If he cannot be tactful, he tries to cover his failing with humility and wit so as to minimize the insult he inflicts through his lack of social skill. This is an artform that he has been learning since birth, and one he values as much as he values skill with a sword.
Since oth Nifft and Mr. Fidget have addressed some of the many ways that the good Paladin could respond at a dinner party, I'll address Oni's challenge.
King: "Is not my Queen the most beautiful of women?" (points toward the queen who looks like a cross between Rosanne Barr and Broom Hilda).
Paladin: "It is as my Lord has said."
or
Paladin: "I bow to my Lord's superior taste and judgement."
or (by addressing the nature of beauty)
Paladin: "Her soul is as radiant as an angel my Lord, and her precence is a blessing to all around her."
or (by deflection with wit)
Paladin: "My Lord, question a chaste man about the beauty of women, and he shall always answer 'Yes'. I'm afraid therefore my opinion on the matter is valueless."
Or any number of other things. If the King has any value at all, he recognizes tact when he sees it and if he values his servant doesn't press the matter. If the King really thinks his wife is beautiful, perhaps he believes that the Paladin idolizes some other woman who he wishes to refrains from snubbing. A similar event occurs in LotR's when Gimli challenges Eomer to a duel if he will not swear that Galadriel is the most lovely of all women. Note how each tactfully averts the duel at various points in thier relationship.
I consider the ability to pass such 'tests' to be the mark of RP quality in Paladin player. If you can't pass them, then you probably have no business being a Paladin.
One of my favorite examples in a real campaign, concerned a Paladin speaking to a 1st edition Barbarian.
Paladin: "I am a servant of Mystra."
Barbarian: <skeptically> "Mystra. Who's she?"
Paladin: "Why she is the Goddess of M...Many Wonderful Things."
