There are some really good suggestiions, particularly the Monster, Madoka, Fate/Zero, and P4, Gurren Lagaan are very good. In fact, Monster is my favourite anime, Madoka being number 2.
SnK definitely is overrated in the sense that it has a lot of pacing issues and really hasn't yet dive into the core of the series so far, even though it's a year and a half into the series. I did not find myself to care for the squad much outside of MC and Mikasa either, so YMMV on it. In comparison to Fullmetal, it's not close in it that Fullmetal managed to make you care about a minor character like Hughes. I can see the appeal, since the anime is very...American in mentality, but the quality of the visuals and sound is very good.
Out of the stuff I haven't seen a recommendation for:
Kara no Kyoukai: it's a series of movies that are deep and relatively unnerving. The animation studio is fantastic and the quality is top notch. If you like Type Moon, this is an easy pick up. If you're into Fate/Zero, this is kind of like a predecessor to it, while still being in the same universe. As a side note: Fate Kaleid Ilya Prisma is in fact a magical girl anime despite being in the Type Moon universe, whereas everything else in the Type Moon universe falls under thriller or supernatural. DO NOT watch Fate/Stay Night and Tsukihime, as neither of those two anime were any good...which is sad since the source material is great.
Steins;Gate: Sci-fi drama, from the minds of Nitro+. This is one of their better offerings, where an unsuspecting scientist(?) discovers ways to Time Travel and uncovers a hidden plot. This is the best of the trio of semi-colon series from Nitro+, with Chaos;Head and Robotics;Notes also set in the same universe. I never watched Chaos;Head, but Robotics;Notes is pretty good with the exact same formula as S;G.
Noein: Speaking of science fiction, Noein is also pretty good. The visuals are quite outdated by now, but the storyline managed to grip me after a rather slow start. As always, there is a time traveling element to this series as well.
Kore wa Zombie Desu Ka (and KWZDK of the Dead): KlK is insanely stylish and over the top. KWZDK is insanely over the top with comedy and also thrives on the similar absurdities that is seen in KlK. For insance, there is a zombie man who is a magical girl in this series. Totally crazy shenanigans.
Yakitate Japan!: Bread-making anime. See notes on absurdities above.
Shiki: I saw some suggestions of horror (Another, Higurashi, Umineko), so check out Shiki. It's vampires done right. Truly frightful from beginning to end, but for different reasons by the end of the series.
Mawaru Penguindrum: The series lays it pretty heavy on you at the beginning to set the tone for this series, and it's crucial for it to be this case in the psychological genre. This series does thrive, at least early on, on absurdities, but really gets deep into the main characters abotu midway into the series. This is more of a drama with comedic elements in the earlier half of the series than a thriller like Monster, though.
Durarara: Someone recommended Baccano!. I'll put Durarara in here as well, since it's very similar, and made by the same studio.