I know that I’m combining characters, but Jack Cassidy had some great lines which may even have been ad-libbed. In Publish or Perish, after Columbo tells Riley Greenleaf that “this man is a locksmith”, Greenleaf sarcastically replies: “Hooray”.
I also love the line in Murder By The Book when Columbo says: “I was in the neighborhood” and Ken Franklin replies: “You’re always in the neighborhood!” He also tells Columbo to continue his theory “as boring as it is”.