I'm just going to toss you some of my favorites.
Monster
A neo-noir thriller that takes place in post-Cold War Europe. If that sounds like a strange premise for an anime, it is. But it works. I can't really go into this without spoiling it.
Fullmetal Alchemist: Brotherhood
You mentioned Fullmetal Alchemist, but I'm pretty sure you meant the original anime series from the 2000's. Brotherhood more closely adapts the manga, which results in a more concise story with less filler and a much more satisfying ending.
Legend of the Galactic Heroes
The animation is old-style and not as high quality as you might expect, but it's one of the most epic space operas ever, anime or not. If I had to sum it up in a single sentence, I'd say it's the tale of one man's journey to rule the galaxy.
Cowboy Bebop
The others would kill me if this wasn't here. It's the quintessential anime. It's about a rag-tag group of bounty hunters in space.
Ghost in the Shell (The Movie)
You may have heard that this is being made into a live action film, but we're not here to talk about that. I will tell you that it's one of the inspirations for The Matrix.
Ghost in the Shell (The TV Series)
This goes against your request a bit, in that it's relatively episodic, but it's worth it. It's basically a police procedural with the same characters, but it doesn't technically take place in the same timeline as the movie.
Samurai Champloo
At once an homage to and a parody of the samurai action genre. It's deliciously anachronistic, stylish, and original. Just watch this video:
Also, someone is inevitably going to tell you to watch Sword Art Online. Don't.
It's a trap.