Let's see...
Samurai 7 is an amusing movie. It's very much "anime that's like people say anime is like," in that it's about samurai cutting apart giant robots.
For less ridiculous and fairly neat action, try Samurai Champloo. It's about samurai ronin really skilled people with sharp things having often absurd, usually murderous adventures.
Cowboy Bebop is by the same people but set IN SPAAAAACE, and has similar overtones with bounty hunters. It has some of the best dark humor I've ever seen, so if you like one, you should probably try the other.
Afro Samurai is very similar in vibe to Samurai Champloo, but infinitely darker and more stylized. I thought it was really cool, but it is a bit on the gory side, and is very short. If you like the not-choppy/adventure bits of it or the choppy bits of Samurai Champloo, consider watching the other.
Little Witch Academia is an adorable standalone mini-movie thing that will probably make you wish there was more.
I can second Fullmetal Alchemist and Hellsing as being pretty good for what they are, which can mostly and lazily be summarized as "magic" and "vampires" respectively. Both have two versions, of which it is generally agreed that the closer-to-manga remakes (Brotherhood and Ultimate, respectively) are better.
Kill La Kill and Tengen Toppa Gurren Lagan are both ridiculously over the top and awesome, featuring giant robots in the latter case and I don't even know in the former. Kill La Kill in particular I dare you to watch for five minutes and not be down for the rest.
Redline features a pompadour. If that's not enough, it features a space elf with a pompadour. If that's still not enough, you're probably a lost cause but it's a racing anime movie. With, you know, guns and such, obviously.
That's all that springs to mind at the moment, and half of them were already recommended or I was reminded of by others.