I see thank many people have recommended you some really classic albums or ones that are very influential, so I thought I'd recommend a few not so classic or even some unconventional choices of mine which some die-hard metal heads may turn their noses away from. I personally think it's always easier to get into more recent material, so the following would be quite, well... recent lol
Waltari - Release Date (2007)
Waltari's a Finnish band that have been around since the 80s, but I don't think the are very well known outside the boarders mainly because they sound very "unorthodox". They are loosely categorised as Alternative, but really, they play a mixture of Thrash, Industrial, Progressive, Avantgarde, Heavy and dare I say Funk and Hip-Hop. I still remember a review said they are a musical UFO. The more important thing is everything flows and sounds natural and exciting. Definitely something for an open minded listener looking for something truly original.
Protest The Hero - Fortress (2008)
Metalcore is one of those genre's that are considered as quite mainstream and hated with passion by "tr00" metal heads. Protest The Hero definitely breaks all moulds and indeed, to classify them as Metalcore is unfair because their music is so much more. Being extremely progressive yet catchy, they are at the same time have a very schizophrenic and insane take on Metal. The riffs here are never repeated over three times and the listener is constantly barraged with chaotic screaming, harmonised vocals, brilliant solos, riffs, choruses etc.
Hope to hear how you get on with these if they are up your league
Then maybe I'll recommend more