Ah, Trigun. I think I watched that one and Cowboy Bebop when I was either in elementary or high school. I've got a necklace with Wolfwood's gun as pendant.

Since I lived in Asia previously, growing up, I think I got to watch a lot more anime on network TV than in the US.
Have you tried watching Vandread? It's a pretty cool post-apocalyptic anime. I think it was one of those anime -> manga things so I don't know about the quality of the manga.
For a more lighthearted read (compared to MPD Psycho, at least), you might also want to try
Psychometrer Eiji. That one deals with serial killers and sometimes delves a bit into supernatural phenomena.