Recommend some books that meet these requirements, please!

1. Dark, brooding, avoids sentimentality
2. Isn't formulaic, doesn't fit snugly into a particular genre, is layered
3. Possesses an underlying beauty and humanity

Quite specific I know, but I'll really appreciate any suggestions. :)

The Portrait of a Lady!!!!
(But then, I would suggest that, wouldn't I...)
Crime and Punishment would probably also fit nicely.

Day of the Triffids by John Wyndham. Great sci-fi horror, Alex Garland/Danny Boyle borrowed from it for their horror film and novelization, 28 Days Later. Many parallels.

Story from the Underground

Name of the Rose or Foucalt's Pendulum by Umberto Eco.

Wuthering Heights and Jane Eyre by The two elder Bronte sisters.

A Clockwork Orange - Anthony Burgess

The Count of Monte Cristo/The Three Musketeers/Les Miserables/The Hunchback of Notre Dame

Rabindranath Tagore's "Home and the World."

I'm not sure if this is gonna fit, but I believe George Orwell's 1984 is quite gloomy, yet has an underlying beauty and humanity!

Nossa, 1984 is indeed a good choice! Beg to differ in the beauty point though :p That Beauty/Humanity point really spoils my advices; I was going to suggest Beckett's Murphy or Watt (haven't yet read Watt till the end, but I definitely intend to).

I have the feeling that you guys are all going to assault me for this, but I think The Little Prince covers all of your points perfectly. You read it in a day, but unless you're heart is made out of stone, or if you consider yourself to be superior to such a (seemingly!) simple book, you will love it.

The Island of the Day Before by Eco

Perfume by Patrick Suskind.

The Island of Dr Moreau by HG Wells

Angels and Demons by Dan Brown

Faerie Tale by Raymond Feist

American Psycho - Bret Easton Ellis
first thing that came into my mind when I saw the requirements.

Anything by E. M. Cioren, Notes from the Underground, Dostoyevsky, The Narrative of A. Gordon Pym, Edgar Allen Poe. quasimodo1

Without renaming any all I can really think of is Lord of the Flies by William Golding... at least in my opinion...

And just for the record, furthermore, Day of the Triffids is one serious piece of literature, definitely one of my unwritten top ten favorite novels of all time (something I find truly hard to list because I am throwing away so many deserved books). As mentioned before, Garland and Boyle basically removed the triffids and green meteorite showers that left the majority of the living human populace blind with that of a contagious rage virus and "zombies" however DotT has so so much more, alot of memorable and original pieces wound within this tale. A major work of literature, can't believe this was written in 1951, a voice so startlingly contemporary with readers today.

How about Nevil Shute's On The Beach, about survivors of WWIII in Australia, whom know nuclear winter and death is inevitable, and attempt to resume to live normal lives.

Robert McKenna's The Sand Pebbles--a story of a US Navy gunboat assigned to China during the early 1900s when communism was spreading there. The story of a misfit sailor trying to cope with the war and his private demons in a land of great beauty and a time of great turmoil.

I noticed someone suggested American Psycho by Ellis, I think a different one of his novels, Less than zero, is more suitable for your requirements.

Right now, I'm in the middle of reading Rabbit, Run by John Updike. So far, it's pretty gloomy, but it's also pretty degrading towards women, so if you have any qualms about that you might want to avoid it.

Asides from that, all I can think of is A Separate Peace by John Knowles.

Thanks a lot to everyone. If anyone thinks of any more don't hesitate to list them. :)

The Road by Cormac McCarthy

Postcards by E Annie Proulx

World's End by T C Boyle

Survivor by Chuck Palahniuk

Camp Of The Saints by Jean Raspail

"Someplace to Be Flying" Charles de Lint
"Neverwhere" Neil Gaiman

I second Aiculík's suggestion: read Umberto Eco's The Name of the Rose.

If you decide to read this book, however, you might want to read a few relevant short stories first, such as Borges' "The Library of Babel" and Poe's "The Purloined Letter." Best wishes!