Seconding Steins;Gate as it's one of my top two favorite anime and you've already watched the other (Madoka Magica) Nevermind, you already saw this
Attack on Titan is also quite good. And, unless I'm forgetting something, absolutely no fan-service to boot. The first half of the first season starts off really strong, unfortunately the second half is a little slow and disappointing. Main character kind of sucks, but the supporting cast is strong enough to make up for it.
I'll also throw in a recommendation for Baccano. It's not exactly the greatest, but I found it fun and interesting. It has a very nonlinear storytelling and you spend most of the anime trying to piece together what happened.
Zontar said:
RahXephon, it's a super robot anime that can be summed up as "Evangelion if it made sense". There's plenty of mystery in it as the characters try to find out what the aliens are and how they are connected to humanity, all while conspiracy abounds within Earth's forces.
One thing that's funny though is they used the Mayan calendar before it was cool (the show is from about 2000/2001ish) so the date is off by about a week for when it happened.
I was looking into Mecha anime a little while ago and noted this one looked interesting. I was deliberating on whether I was going to check it out, as someone who came so close to liking Evangelion (ended up hating it) I think I'll give it a look