Come to think of it, the music video for "The Barry Williams Show" gets pretty creepy when the audience in a Jerry Springer-esque show suddenly begin to bleed until the entire stage is literally flooded with their collected blood. To top it off, the actor portraying Barry Williams is left stranded on a raft in the middle of it all until falling in at the end.
And one for the road: I Don't Remember. The song, at least on the album (the video uses a heavily edited live version) is nightmarish enough on its own, but the video... Have fun trying to get used to leather couches again.
"Moribund The Burgermeister".
"The Tower That Ate People".
Peter Gabriel's various CG versions of himself in the music video for "Steam". This one takes first prize.
"Mercy St" is probably his most nightmare-fuelled song, and actually contains many word-images that wouldn't be out of place in a Gothic horror film- it is in fact an ode to the suicide of poetess Anne Sexton.