As far as dark heavy classical goes, I second Mahler and Shostakovitch symphonies. Also check out Mahler's Kindertotenlieder (Songs of the Death of Children). Bryn Terfel has a good recording on which they are paired a little incongruously with arias from the Mozart-Daponte comedies mentioned earlier. Another great Mahler symphonic songcycle is Das Lied von der Erde.
There's some wonderful choral music, especially requiems, that is very dark. Some have been mentioned, but here are some of my favorites: Johannes Brahms' Deutsches Requiem, Benjamin Britten's War Requiem, Mozart's Requiem in D Minor, Guiseppe Verdi's Messa de Requiem.
Penderecki-Don't just get Threnody, it's good, but he has some wonderful dark and somber sacred choral music like the chilling St. Luke Passion and the much more recent, and more accessible Credo.
Speaking of passions, get both of Bach's passions,St. John Passion and St. Matthew Passion, they are about as dark as Baroque music gets. For earlier German baroque, check out Heinrich Schutz. eMusic has a great recording of Muzikalische Exequien (Deutsche Begrabnis Missa, German Funeral Mass), written for his employer's funeral. It's performed by the Sixteen, one of the best early music vocal groups.
On opera, Don Giovanni has its comic moments but gets really dark and foreboding, especially at the end. There's so much great dark and heavy opera its hard to suggest just a few, but in addition to one's already suggested, try Puccini's Turandot, left unfinished at his death. There's a long tradition of operas about the devil, like the several based off of Goethe's Faust. eMusic has a great cd from the legendary American bass Sam Ramey, called a Date with the Devil.
Khar, have you ever listened to Mussorgsky's masterpiece opera, Boris Godunov? As an opera overall it would probably bore you, but there are some parts that would probably stick out as entertaining if you love St. John's Night on Bald Mountain.
Wow...ridiculously long post...not a good idea to get me started on European art music ("classical")