Pink Floyd’s album Final Cut is very dark, but not very heavy.
Gloomy Sunday is a dark song when you leave off the tacked on “it was all a dream” ending some artists use. Galas does a great version of it.
I’m not sure why, but I find several albums by Porcupine Tree very dark: Signify, In Absentia, and Deadwing.
Opeth is frequently both dark and heavy.
“JC Auto” by Sugar (sorry, no Youtube clips) is very dark and heavy, though more punk than metal.
GWAR has made a couple heavy albums lately but in the past they experimented with everything from jazz to punk to ska to rockabilly to some stuff that their female singer did that sounded kinda like showtunes, etc etc. Even their recent heavy albums wouldn’t be called death metal by most.
Seeing as how some of the heaviest and darkest music of the past is orchestral, here’s my obligatory shout-out to European symphonic metal.
Tristania - “Wormwood” (Norwegian)
Sirenia - “Euphoria” (Norwegian)
Epica - “Blank Infinity” (Dutch)
Within Temptation - “The Howling” (Dutch)
Nightwish - “Cadence of Her Last Breath” (Finnish) (new singer)
^— I couldn’t decide between that and “Amaranth” so you get both!
Nightwish - “Ghost Love Score” (Finnish) (old singer) (this song is freakin’ epic - the first time I heard the thematic recap at 7:43, I was literally knocked on my ass - then I saw this performed live, and teh awesomeness nearly left me lobotomized)
^— For those with less epic appetites, The Siren and Higher Than Hope are acceptable mini meals
For the metalcore among us:
In Flames - “My Sweet Shadow” (Swedish)
As I Lay Dying - “Confined” (USA)
Killswitch Engage - “When Darkness Falls” (USA)
For the industrial darkwave lovers:
Collide - “Euphoria” (USA)
And two staples in dark, creepy American rock:
Tool - “Prison Sex” (disturbing!)
Deftones - “Digital Bath”
Is dark metal-dance acceptable? If that’s within your realm, then…
You haven’t lived until you’ve listened to E Nomine. Bible versions or monster visions, done in Gregorian chanting–oh, and did I mention it’s in German, and therefore eight millions times more awesome?
“Mitternacht” (“Midnight.” Perfect for Halloween music.)
“Schwarze Sonne” (“Black Sun.” To inspire the badass within.)
In fact, pretty much everything from their album “Finsternis” (“Darkness”) would be right up that alley. With such titles as “Das Tier in Mir” (“The Animal In Me”), “Die Schwarzen Reiter” (“The Black Riders”), and “Dracul’s Bluthochzeit” (“Dracula’s Blood-Wedding”), where can you go wrong? 
Thanks for the awesome list, guys. We’ll be checking this out. Is this mostly death metal? “I don’t like most death metal because it has no rhythmic quality to it. I like the sort of demon snarling melodic riffs of Cradle and Dimmu Borghir. I also like music to have really cool lyrics. Have any of you checked out Disturbed’s Inside the Fire. Those are some amazing damn lyrics.”
My friend loves Satanic music and anything that counters Christianity. (We have interesting discussions.) She really wants some music that’ll just creep her out or transport her or “just freakin’ carry me away.” Does anyone have any more to add to the list we will be checking out.
Not metal, but as it happens, I’m listening right now to the Original Soundtrack for Silent Hill (the video game). More like creepy ambiental music.
Emperor, Ihsahn (who is from Emperor), Arcturus (well, some of it - look up “Alone”, but not the live version from the DVD), Ulver (these guys don’t just do metal, but please find Nattens Madrigal and then listen to the whole thing in a row - wow!), Amon Amarth, Bal-Sagoth, Akercocke, Ayumi Hamasaki (hehe, just kidding on that one).
Seconding Burzum. Am intrigued by this thread and may check out a few of these bands myself.
Normally, I would have more, but I took a sleeping pill an hour ago and am a wee bit out of it as it kicks in.
I like a lot of happy/fun metal too that I keep wanting to recommend, but it doesn’t seem like that’s what you’re looking for. 
From Supersession by Al Kooper, Mike Bloomfield and Steven Stills, their cover of Donovan’s “Season of the Witch.” Unlike the LP, the CD includes the original version without the horns that were dubbed in later. Most folks seem to prefer this one.
“Piggy Pig Pig” and “Dead Man’s Dream” on Procol Harum’s Home. “Monsieur R. Monde” on Procol Harum’s Exotic Birds and Fruit. “Repent, Walpurgis” on their first album. Man, if you like creepy music, you gotta listen to “Repent, Walpurgis.”
The title of the op made me think immediately of “The Thing that Should not Be” by Metallica. If you haven’t heard it (I think it’s waaaaay more mainstream than some mentioned here), imagine Cthulhu’s entrance music.
I recently discovered Electric Wizard. They’ve been called the heaviest metal band of all. Not the most evil, but sort of heavy stoner music. I’m not a stoner but I dig it. Careful with your sound systems on the actual CDs, the low bass is hard on woofers.
Skip Burzum. While it’s some decent music, Varg Vikernes is a Nazi jagoff.
I always find it interesting that people avoid Burzum because of Varg’s positions on cultural purity (which are a little different from Nazism) and not because he’s a murderer and very likely an arsonist. In my mind, being a violent criminal is much worse than holding abhorrent views.
Prison is punishing him for the murder, I’ll punish him for the political views by ignoring his bands. Burzum seems to be making out of the underground and more and more on to the cultural radar and that bugs me. Don’t give that asshat any goddamned money people. Black metal and it’s outgrowths is interesting music but it’s fraught with terminal assholes such as the guys from Gorgoroth.
Sounds like you (or your friend - who are these recommendations for?) might like Valhalla Awaits Me by Amon Amarth. It’s death metal, but it’s very catchy, and you can understand all the cool lyrics.
Almost forgot to mention Strapping Young Lad. In most cases though, you probably won’t understand the lyrics.
I just saw Amon Amarth a couple of weeks ago, which was amazing. 
Just because I really like this song, here’s a link to Arcturus - Alone. The song uses the Edgar Allan Poe poem Alone as lyrics.
Does this sort of thing appeal to you? I don’t know how to describe it, but it’s definitely awesome. It sounds happy rather than dark, but is definitely heavy. 
And the video is great. Finntroll - Trollhammaren. I saw these guys a couple of weeks ago and they just blew my face off with awesome, as well.
I think Fintroll is considered folk metal, and along those lines there is also Korpiklaani, who is also awesome.
I see Ultrafilter already beat me to it (as I should’ve suspected), but anything by Shape of Despair. Dark, heavy, and evil.
Yeah, they’re great too. 
I thought of mentioning them as well. I just thought that they were maybe too happy-sounding, even more so than Finntroll… I don’t find them dark at all.
But definitely good stuff!
Check out the album Prayer For Death by Entrance. Almost every song on it would qualify here…