Ooo,I second Patrick Stuart!!
On a serious note, Norm Sherman would be a great host. He would surely be different, but I don't think it would be as jarring as the starship sofa guy. I could see him doing a weird news segment or writing/performing a hilarious song.
Also, the guys from Dunesteef podcast would be fun I think, and I also agree with Air Out My Shorts.