I'm looking for some new music and thought it'd be a good idea to ask this community.
I like narrative music like Marty Robbins's El Paso. Music that tells a story appeals to me greatly if it's a good story.
I like vocal harmony. Gregorian chant is a good example, as is African tribal music.
I like unusual voices because singing along exercises my ability to imitate. (Bright Eyes, Rammstein, Leonard Cohen.)
I think you might mean Renaisance music (like Palestrina, Byrd, Des Prez), not Gregorian Chant, since Gregorian Chant is usually monophonic. But anyway, I'd suggest bluegrass if you like vocal harmonies and interesting voices. For the former I'd got with the Seldom Scene (who have been around for a while) perhaps their album Act I or their live album At The Cellar Door, and for the latter maybe Ralph Stanley's more recent albums (if the Seldom Scene have been around for a while, Stanley's been around for fuckin' ever). The big minus I could see given your description of your tastes is that most bluegrass song structures are pretty verse/chorus oriented (if someone did bluegrass-based postrock that didn't turn into a hippy jam session, I'd listen to it), but I'm also not a huge fan verse-chorus-verse etc. but Bluegrass is still probably one of my favorite genres.
A decent intro to the genre as a whole (along with gospel, et al) is probably the O Brother Where Art Thou? soundtrack, which you've probably heard already.
Also, for weird vocal Tom Waits is pretty well-known and at least on some albums (Alice, for instance) pretty accessible.