No one's mentioned my second favorite comedy-music act, Melbourne (Australia) comedy-music duo Scared Weird Little Guys. The Scardies (as they often call themselves) are two dudes, John and Rusty, from Melbourne whose act went from general comedy to musical comedy and although I'm crazy about their CD "Scared," I think they hit their peak with their live CD, "Live at 42 Walnut Crescent," which features, among other things, a song where they sing the phone book (sounds boring; it's hilarious), a parody of the Macarena, and a cover version of Prince's song "Kiss" done in every imaginable musical style (rap, reggae, country, etc.) Bet they didn't get permission for that one! Anyway, I highly recommend their CDs if you can get 'em...they're sometimes hard to find outside of Australia.
I'd give my left arm to see these guys open for Al. And I agree with buying the Dr. Demento collections; there's certainly some must-have stuff on those, but the Demento Society Basement Tapes CDs are even better, and the only way to get those is to be a member of the Demento Society (well worth it; I've been a member since the beginning, 12 years ago), so I'd recommend going to His Official Site
and joining right away if you're not already a member.
And the Scared Weird Little Guys' site is here
if you want to get a look at them, but sorry, they're not studly hot fellows like our Al.