Zappa and Waits are both one-of-a-kinds... and i'm huge fans of both.
in the vague realm of Waits, i'd recommend:
Nick Cave - dark, gothic and highly literate.
Elvis Costello - the other great songwriter of the 70s/80s/90s.
Vic Chesnutt - highly personal songs that reveal more with each listen.
Zappa is trickier, as he's not just a songwriter, but a virtuoso and composer:
Captain Beefheart - his bizarre masterpiece, Trout Mask Replica, isn't for everyone, but it was produced by Zappa. they grew up together.
John Zorn - +1 for this. no humor, but a great avant gardist. his more recent material with various incarnations of his Masada project are the most accessible.
Funkadelic - this might sound strange, but they had a pretty off-kilter view of the universe, great instrumentation and virtuosity. they are brainfood for the booty. (as they say, free your mind and your asswill follow)
Frank Zappa - if you really dig Zappa... just buy everything in his discography. it's pretty large, so i imagine you haven't completed your collection yet.