Dick Gautier never appeared with Columbo to my knowledge...but his wife did!
Dick was married to Barbara Stuart, who played Claire Fleming (the murder victim) in "Enough Rope", the 1961 TV drama that marked Columbo's first appearance.
See the Scrapbook article, "Enough Rope - The Very First Columbo". It's also linked from the home page.
Barbara is best remembered as "Miss Bunny", Sgt Carter's girlfirend in "Gomer Pyle, USMC". But before that, she was the very first murder victim to be avenged by Lieutenant Columbo.