I am by no means "hardcore" into the anime world, so Ill stick to reccomending what I know, and try and provide information to possibly assist you in watching/not watching something I reccomend.
Some of what I will reccomend have been mentioned, but I will reiterate:
Berserk - My favorite anime series ever made. HOWEVER, this comes with a warning. The anime series is almost entirely character build up, and the story STOPS after the biggest turning point. If you do not read manga, this anime WILL dissapoint you. However, if you do enjoy/read manga, and are willing to read through about 8000 pages (33 issues x ~200-250 pages per) the story is fantastic, the action is amazing, and the little bit of lighthearted humor (via Puck). If you have no intention of reading the best currently running manga in existence(IMO), don't bother watching the Anime. (for reference, my folder of unzipped Berserk manga is just about 2 gigs). Also, the scene in which Gatsu gets the Armor of the Berserk (where my icon is from) is an amazing issue.
Elfen Lied - Another one with a warning. It is INCREDIBLY violent, and contains many images of young female nudity. I enjoyed the plot from start to finish and I enjoyed the character of Lucy/Nyu, but it certainly is not for everyone.
Perfect Blue - Mentioned before by someone else, a great Hitchcockian thriller. If you like psychological thriller/mysteries, its a great watch, and at least in my experience, something completely atypical of a "standard" anime drama / movie.
Texhnolyze - a weird, but intriguing collection of episodes... explaining them doesn't at all do them justice, but it focuses around an underground world and the technology there. Made by many of the same people who gave us the fantastic Serial Experiments: Lain, so take that however.
Spriggan - there is some plot, but its far more of a turn-your-brain-off-and-enjoy-the-amazing-action-sequences.
S-Cry-Ed - the manga for this series is shit, but the anime took a shitty manga and turned it into something amazing. On the surface, its a mindless action foray dealing with people with powers known as "Alters" that allow them to take matter around them and reform it into something else (usually representative of their character) the main character wraps his arm in armor and punches things, another characters alter is to make a giant smashy robot, etc. It isnt the deepest anime ever made, but it does touch on a lot of public issues, and the characters are incredibly well developed. The plot gets a bit goofy towards the end, but all in all, an amazing series.
Neon Genesis Evangalion - as other people have said, its VERY angsty, so its definently not for everyone. And the series does kind of fall apart towards the end, gives you more questions than answers, and the two "follow-up" movies dont help very much. However, I still find it interesting and enjoyable (if a bit tedious at times).
RaXephon - Neon Genesis Lite. It is very nearly the exact same story, a lot faster paced, better action, and less "God" thrown around. A much more enjoyable watch than NGE, if not as deep. Also, don't bother with the movie, its the same story as the TV show, condensed into ~2 hours.
Wolf's Rain - Very heavily seeped in Japanese mythology / culture. I've read that the series makes far more sense if you know a lot about Japanese history / culture / mythology, but all in all, still a good series, if approaching the angsty side a bit much.
Hellsing - watch the Ultimate version, no contest. Vampires, big guns, action, Alucard, etc.
Vampire Hunter D - similar conceptually to the "Blade" movies, but more atmospheric, a VERY non-traditional plot, set in the future, despite how it looks. But, theres still a decent bit of action and blood, so if you are into that, its definently worth watching.
Ninja Scroll - Both the first move and the short series (I wasnt a huge fan of the second movie). Predominantly action oriented, but a decent story as well.
Other titles of note:
Gantz - I dunno about this one... Ive watched the first 8 episodes, and Im having an incredibly hard time staying interested in it. Everything involving the room and Gantz itself is interesting, but the whole subplot with the main character and the girl is awkward and distracting IMO.
Burst Angel - Ive only watched one episode, so I cannot truly make a "OMG U SHUD WATCH DIS" reccomendation, but it did catch my interest, I just havent had time to keep watching. Seems (and I could be off base) to be action oriented / less plot.
The SoulTaker / Soul Taker - I remember enjoying watching this series, but getting so lost watching it, and having a hard time keeping up with the story. Its weird, and I remember it being a bit convoluted, but possibly something worth checking out.