Oh, PLANETES! Yeah! Like Maison Ikkoku, it’s the sort of thing that US TV would try to do live-action & not even think of doing animated. But it’s near-future hard SF. Episodic stories set in a space station. Actually, the show it always reminds me of is a short-lived US show called LAX, set in an airport. Very ymmv, but nifty as a non-“anime” anime.
“I’m just the temp.”
The Lupin The Third franchise is fun.
That reminds me of Detective Conan/Case Closed (which came on right before Lupin III on Cartoon Network for a while.) It’s what I imagine happened to Encyclopedia brown after he grew up, started taking on murders, and then got turned back into a little kid. Also, with the kid secretly solving everything, it has hints of the Inspector Gadget/Penny dynamic.
But mostly I liked it because, unlike many detective shows, you actually had a chance to figure out what had happened before Conan tells you, yet it wasn’t too easy.
Granted, I haven’t seen the later episodes, but I vouch for the early ones.
I love Scrapped Princess (“Sukurappudo purinsesu”). Trailer.
Very formualic swords-and-sorcery (very minor spoiler since you find this out in episode 2) : that really isn’t sorcery
The princess is born and there is a prophecy that when she becomes 16 she will DESTROY THE WORLD.
So the king orders her thrown off a cliff (hence the title 
) but the queen has her saved and placed with a brother (kick-ass swordsman) and sister (kick-ass mage) to be raised in secret.
Although it’s almost by-the-numbers I think that all the pieces, art, music and characters just hit a sweet spot. I find it feelgood that’s not totally harmless.
If you like the sword-and-sorcery type of medieval fantasy, then perhaps The Twelve Kingdoms will appeal. It’s set in a world that resembles medieval China, but which can only be reached from Japan or China by a kind of magic. It’s based on a light-novel series which has only partially been translated into English, and the anime series has 45 episodes, falling generally into four story arcs.
In two of those arcs, Yoko Nakajima is the central character. She starts as a high-school girl in Japan who tries to please everyone, and so has no friends, but who is made the monarch of one of the twelve kingdoms in the first episode (though she only realises this much later), and is transported to another one in the first episode. But she has to embark on a long voyage of self-discovery, fighting demons, fighting mistrust of others, and fighting starvation and abandonment, before she can claim her kingdom. Then her real fight starts: she has to deal with her ministers, with a neighbouring king who wants her killed, and with a rebellion from a provincial governor, before she can really start governing her kingdom. It’s a long story, with some weird things, including a very weird reproductive biology, but I’ve enjoyed both the books and the anime. And if you want strong female characters, it has them, especially Yoko, who grows in strength throughout her story arcs.
So many great shows/movies have already been mentioned. So, I’m going to go ahead and recommend a few older favorites of mine. Not sure if they’re necessarily what you’re looking for, but I urge everyone to check them out:
Legend of Galactic Heroes
My favorite animated show, Legend of Galactic Heroes is a 110 episode OVA detailing the conflict between The Goldenbaum Empire and The Free Planets’ Alliance. This show is epic in scope with hundreds of characters and pretty much everyone is memorable in some way. The plot involves warfare, political intrigues, love, clashing ideologies and other juicy stuff. Did I mention that the storytelling and characterization is the best I’ve seen in any anime? Highly recommended.
Fang of the Sun Dougram
The best mecha (giant robot) show I’ve seen so far (honorable mention to Votoms, but I haven’t finished that one, yet). Dougram is obviously inspired by the original Mobile Suit Gundam but, in my mind, improves upon it in several ways with a tighter, more mature story and a more likable protagonist. That’s not to say that some of the works in the Gundam aren’t worth checking out to, but for me, Dougram is the winner.
Galaxy Express 999
The movie, I haven’t seen the series but the movie is splendid and a great introduction to the universe created by Leji Matsumoto.
I’ll try to think of more, later.
I’ve had LoGH on my list for years and just never got around to it - honestly, I’m waiting on the slight chance of a domestic release, because the, um, other distribution channels don’t appeal to me for 110 episodes. 
I have seen LoGH lite, aka Tytania, and adore it.
Not a fan of anime, generally, but back in the '90s, there was this one tv show I’d get up early to watch: Samurai Pizza Cats.
It was so funny, it was if the Canadians who adapted anddubbed it were high at the time .
I always plug Martian Successor Nadesico in these threads. A fantastic parody of / homage to Star Blazers / Robotech / Voltron. It’s particularly notable for it’s concept of anime fans.
Let’s go Gekigangar!
Maybe not high, but definitely flying blind. Story goes that the dubbers either had no transcripts from Japan at all, or the ones they had were very badly translated. So they just made up the stories and dialogue as they went along to match whatever was in the animation. Kind of like what they call a Gag Dub, only it’s official.
To add to my earlier suggestions, Macross Frontier is the latest and I’d say probably the best of the Macross franchise. Great battles and a strong story to boot.
I think you’d really like Utena, olives. I don’t watch much anime anymore but it remains a series I love to go back and re-watch. I have all the soundtracks as well and it’s just an amazing story to follow. It starts off like a typical shoujo battle story and starts slowly morphing in a postmodern tale with really really crazy characters. Go watch it! And then watch the movie version. I still have all my old plushes I collected in high school from the show 
Another new show that I really enjoyed was Wolf’s Rain. Again, great music selection and well-drawn characters. The story is that in a post-apocalyptic future, humans live in small bubbles of protected cities and animals like wolves are extinct. However we meet 4 men/boys who appear to be wolves in disguise as humans, and they are trying to find a paradise where they can live. My favorite characters are the detective trying to track down the rumored wolf and his ex-wife IIRC who follows him. Really fun and beautiful story. It’s been a while since I watched it so I probably just summarized it all wrong, but it’s worth a watch.
Check out anything by the late Satoshi Kon. I think Millennium Actress would be right up your alley.
I’d like to second the suggestions of both Ergo Proxy and Rurouni Kenshin. Beware though that Kenshin ran for something like 92 episodes so be prepared to get into it and spend many hours watching.
I think Kagero is pretty badass.
Ha ha ha ZETTAI UNMEI MOKUSHIROKU 
I have all the versions on my iPod, they’re so wonderfully epic and cheesy.
I nearly liked it. Planetes suffered from a comedy/culture cliche that is normally just annoying in most shows, but for me made it nearly unwatchable. It had a couple of “comic” relief characters whose sole function is to barge into scenes screaming loudly and pratfalling. No clever writing or humor in the dialogue…just screaming loud=funny. Did I mention loud? It wasn’t anything lost in translation either, the japanese track was equally brash and irritating.
We’re the chick.
The egg is the world.
Smash the egg’s shell.
For the revolution of the world!!
Or something like that. Oh, those crazy kids and their duels.
Oh, and as long as we’re talking about Utena, let’s not forget it’s obvious inspiration: Rose of Versailles. The story of a young woman whose father, tired of having only daughters, decides to raise her as a man, leading to her becoming the bodyguard to Marie Antoinette. Great show. Sure, from what I can tell it takes some liberties with certain historical figures, but it’s not like it’s the first work of historical fiction to do such a thing.
Well, I can vouch for a number of suggestions here, so far—especially anything that’s Read or Die related—but if I may suggest Bubblegum Crisis: Tokyo 2040? It’s a remake/reimagining of the original Bubblegum Crisis series (of which I’ve only seen a couple of episodes). And naturally, as you can tell from the typical anime naming convention, it’s basically Blade Runner crossed with Batman and Iron Man. Only with women.
But I think I can safely say that it doesn’t depict women as subservient or over-idealized gender conformists, and has "emotional bonding and personal growth theme"s. And robot-zombie fights. And rock music.
And the ending doesn’t leave you wanting to mainline Prozac. Always a plus. 
I liked Ouran High School Host Club. It’s different from most shojo anime in that the heroine, Haruhi, is a practical, no-nonsense girl - the whole gender confusion that sets the series in motion in the first episode happens because, shortly before she started high school, someone put chewing gum in her hair, so she just cut it all off (I guess they don’t know about using peanut butter to remove gum from hair in Japan). The boy she first meets, Tamaki, is the romantic, flighty club president and self-styled “father,” who immediately takes a shine to Haruhi and takes her under his wing, thinking she’s a boy. Once everyone finds out she’s female, he likes her even more. All the other boys in the club are different “types” - the scheming brain, the troublemaker twins, etc. Basically it’s a harem comedy, except it’s one girl and several guys. I’m not sure what you’ll think about episode 7, when they go on a two-day trip to the beach. Kyouya pretends to try to force himself sexually on Haruhi, but backs off. Supposedly he was trying to show her that, as a female, there are things she should be careful about, like potential rapists. :rolleyes: Also doubtful about episode 9 - it involves some girls from an all-girl school (read: lesbians) trying to convince Haruhi to transfer with them. One of them makes a misandrist speech, and Tamaki counters with a speech of his own that is rather homophobic, mostly because he’s not-so-secretly in love with Haruhi and refuses to give her up to anyone, male or female. Personally, it was the low point of the series for me.
I second the recommendation of Black Lagoon. If only I had the body to cosplay as Revy… she’s so badass.
Am I still allowed to mention Naruto? I’ve liked this manga/anime for several years because of the characters, including several awesome females. Even thought it does have a bit of a traditional attitude to females to some extent - the adult female characters tend to be never-married, childless fighters, and the few (living) mothers who appear tend to be seen at home making lunches or, in one case, training dogs rather than fighting. The one female character who does get pregnant so far hasn’t been seen fighting since she had her baby - maternity leave or retirement? Not sure. Personally, I’m not a big fan of Sakura, especially at the beginning when she spends most of her time chasing Sasuke and treating Naruto like dirt, but you have to admit she does grow as a character, and becomes a super-strong, capable medic ninja. She is trained by Tsunade, a legendary kunoichi who returns from self-imposed exile to become the first female Hokage. My favorite is still Hinata. She’s shy and withdrawn, and at first she seems to be mainly defined by her shyness as well as her crush on Naruto, but she proves to be more interesting than that when she stands up to her resentful cousin and fights him. She gets her butt kicked anyway but at least proves she’s a better ninja than everyone thought she was, and finally gets Naruto to notice she exists. She also grows as a character as the series progresses, taking the role of the sweet, demure “princess” type, but no less capable as a tracker ninja and a fighter when she needs to be.
I remember watching that episode. In what had been a very good but not horribly atypical series before that, I started thinking “No. No, they’re not going to go there. That’s just my sick imagination. They’re not going to… surely they wouldn’t go so far as to…”
I was curled up and quivering by the end of that episode and realized that this was the turning point: anyone watching would either say “This is HORRIFYING” and refuse to watch another minute… or say “This is HORRIFYING” and frantically watch the rest of the series.
Sekai wo kakumei suru tame ni!
Have you guys seen the muscial? It’s awesomely cheesy (though the girl who plays Dios in the musical is Kenshin’s voice actress, so that’s kind of amazing). I kind of love the student council number best.
Anyway back to recommendations. I haven’t seen the TV series made more recently, but the original video series of Record of Lodoss War is really great.
There’s really no need to watch the last 30 episodes, though. They’re awful.