This only happens to me when my reputation is at least 18. I go into the Three Old Kegs Inn and this little gnome fellow comes up to tell me that I shouldn't go near this paladin in the harbor area, because of my reputation. He says only during the day can I meet with this guy, but when I wandered all around the docks map looking for him, I never ran into any paladin with an inflated ego.

IIRC that Paladin is in one of the pubs there.
Minor spoiler
.
.
.
.
.
.
.
.
.
.
.
.
.
.
>I think he asks you some obnoxious questions and if he isn't satisfied with the answers (read: when he thinks you're evil) he will attack you.