Months later I found motivation to track it down. I emailed Hawai'i Public Radio and they eventually told me it was mostly likely a syndicated show out of Cleveland hosted by Robert Conrad. I found their programming schedule and emailed him for confirmation; it was Nichols and May, a comedy duo. The album I'd heard was called Nichols and May Examine Doctors.
Turns out Nichols also directed the Catch 22 film.
There isn't much to see on Internet about these two, YouTube has a few clips though.