Several (actually, all, now that I think about it) are rather into anime. So, to succumb to peer pressure, I decided to follow suit. I enjoyed Babylon 5 and the current Battlestar Galactica; my ideal series would be something with an involved plot and some serious world-building. I’d prefer if it not echo the gratuitous repetitious action scenes found on the kids-oriented anime programming that I’ve seen. Soo…any suggestions? 
Well, I’ll jump in with some of my favorites:
Cowboy Bebop - A ‘flying around the solar system trying to make a buck’ story. The characters are pretty good and the animation is fantastic. Each episode is pretty much self contained, but there is an overall story that really picks up steam at the end of the series.
Outlaw Star - A lot of similarities to Cowboy Bebop. The animation isn’t as good, and the characters a bit more ‘immature’, but the story is pretty interesting. It’s less episodic & more of one overall story.
Robotech - my personal favorite, perhaps unreasonably. It’s got your giant-robot stuff, but again decent characters. Minmei’s singing is atrocious, but it has one (well, two) of the best love stories in anime.
Martian Successor Nadesico - Kind of a ‘Robotech Lite’ - it doesn’t take itself very seriously, but has a great gimmick - the characters watch an anime show called ‘Gekigangar 3’. Some funny moments.
Trigun - kind of a post-apocalyptic western. The series stars off lite & fluffy, but takes a serious turn in the middle. Again, strong characters & a decent story.
For full disclosure - lots of people loved “Ghost in the Shell” (the movie), but I thought it was boring & predictable. I also didn’t like Neon Genesis Evangelion, or even Akirawhich has to be some kind of unforgivable sin in the anime world.
My favorite of the SF style of Anime (what I think of when you say “Anime”) are* Akira *and Ghost in the Shell.
My favorite Japanese Animation, which I don’t think of as Anime–in fact, pretty much my favorite animation, and right up near the top of my favorite movies of any kind–are the movies of Hayao Miyazaki and his Studio Ghibli: *Princess Mononoke; Porco Rosso; Spirited Away; My Neighbor Totoro; The Grave of the Fireflies; *etc.
A lot of people seem to not like Ghost in the Shell, especially the movies (which, yeah, are pretty boring. Good, but boring). I personally prefer the series, which suffers from some of the same problems the movies do (Yes, plural, there’s two now), but comes in half-hour snippets and generally is more interesting, IMHO anyways. I’ll admit to being a giant fan-girl, so keep that in mind when I recommend this to you.
From my own watching habits, which tends to be a bit more kiddish–
Fullmetal Alchemist–pretty similar to our world a few decades ago, similar technology but everything runs off alchemy, not science.
Crono Crusade–I haven’t had the chance to watch all of this unfortunately. Takes place in New York near the begining of the century–a nun and a demon team up to kill demons. Not a lot of world building really but pretty interesting.
Scrapped Princess–I’ll admit I didn’t care for this all that much, but I’m throwing it in here because I think there might be a possibility that you might. Basically, it’s about a princess who was suppossed to be ‘scrapped’ (thrown off a cliff) at birth, but was saved and is suppossed to cause the end of the world on her next birthday.
Also, this one isn’t out here yet, but the licensing is starting to get underway already, so I’ll throw it in–Blood+. It’s a semi-sequel to the movie Blood: The Last Vampire (I say semi because while it takes place afterwards, I don’t consider it in continuity, especially after having read one of the novels based off the movie–it’s also watchable without having seen the movie). The movie doesn’t have much of a plot to it, but personally I enjoyed it. It’s about an immortal girl who’s job it is to kill these monsters—but in the series she has lost her memory. The book is called Blood the Last Vampire–Night of the Beast–it reads much like the GitS movies watch, so if you don’t like those I doubt you’d like this either. (And again, I’m a bit of a giant fan-girl). The movie and book take place during the Vietnam war, the series is modern-day.
Blah, it’s Chrono Crusade, not Crono, I can never remember how that’s spelt…
It doesn’t exactly fit the criteria of the OP, but one of my favorite anime series’ is Kino’s Journey. It’s about a girl/young woman (I don’t think it says her age) who travels on a talking motorcycle, having philosophical discussions and visiting different countries.
I’m pretty sure there’s no overall story, but I haven’t seen the entire thing. The episodes sometimes are like sci-fi stories, reminiscent of the Twilight Zone. For example, the first episode is where they visit a country that at first seems entirely inhabited by machines, until they find people scattered in the countryside and learned why the people cannot stand to live together. Then there’s an episode where they visit a country where nobody has to work because they have machines to do things, but people actually work harder.
I’ll second or third the recommendations for Cowboy Bebop and **Trigun **-- I enjoyed both series immensely.
Like others, I enjoy Ghost in the Shell (and its sequel) but find them boring at points. I think the Ghost in the Shell:Stand Alone Complex TV series is f***ing awesome, with the second season (through the first three discs, at least) being better than the first.
**Read or Die **is a great short film – super and non-super agents working for the British Library have to save the world. Great-looking and very well done. Like many other good anime movies, it spawned a TV series (ROD: The TV), which is very good. It’s not futuristic, but does have science fiction elements, and a lot of worldbuilding stuff (in the TV series).
Sticking to the Sci-Fi end of things… I like Kiddy Grade a lot. It’s got a somewhat offputting level of fanservice (panty shots and jiggling boobies), but if you can get past that, it’s amazingly well-done science fiction/superhero stuff.
**The Big O (which is not a porn movie) is a giant robot near-future-ish series, set in a city where everyone has lost their memories. Our hero is basically Bruce Wayne, but instead of dressing as a bat to fight crime, he puts on a skyscraper-tall robot suit.
**
Crest of the Stars is reputed to be very good. I have seen part of it, and find its pace to be kind of slow. I will be returning to it.
For anime research purposes, I really like Anime on DVD. I sometimes disagree with the reviews, but they provide a lot of good information.
*Big O is good, definately.
I’ve always been fond of Escaflowne, which has quite a bit of clockpunk fantasy world-building and non-gratuidous action, though personally I thought it drifted a little too far into into metaphysical interpersonal stuff towards the later episodes.
Last Exile—this is the most gorgeous series I’ve ever seen. Kinda like a steampunk Crimson Skies or The Rocketeer. Pick it up, you won’t regret it. Do it now.
Bubblegum Crisis: Tokyo 2040—Remake of the original series. Good stuff, nice adventure, and it has a finale that doesn’t leave you wistful and vaguely suicidal, unlike a lot (Read: damned near all) of other anime shows.
Miyazaki’s films, also, are great, beautifully made, and have endings usually more upbeat than Dostoevsky novels.
And of course, Fullmetal Alchemist and the Ghost in the Shell series’, which are indeed f***ing awesome, and damned addictive.
I love Samurai Champloo, which is set in ancient Japan, but is rife with anachronisms… it’s got 3 main characters (the plot loosly follows their kind of epic journey across Japan), lots of sword-fighting and other great action sequences, but also has a lot of influence from hip hop. Kind of weird, but definitely satisfying.
And I’ll third (?) the Ghost in the Shell Stand Alone Complex: it’s great.
Another chiming in to add votes for Escaflowne and Big O.
I’d also suggest the El-Hazard OVA series. Very much a bit of homage to all sorts of pulp fantasy stories. A bit of 1001 nights, a bit of Barsoom, and a lot of it just itself, and fun.
For a bit more serious anime, I’d suggest Gasaraki. This is a bit of a “talking head” story, where much of the plot isn’t action, but rahter political and philosophical. Having said that there’s a lot of action, and the politics is a very interesting look at the the US, I think. Technically it’s giant robots, but it goes beyond that basic genre.
I’d also suggest one of my favorite giant robot shows: Patlabor. Basically it’s about a future Japan (1999, IIRC) where giant, man-shaped robots are used in all sorts of construction fields. And have become a kind of crime that requires the police to have robots, or labors, of their own. It’s been best described, in my opinion, as Hill Street Blues with robots.
Based on your mentions of B5 and BSG, I’ll echo the nomination of Cowboy Bebop. Along similar lines is Trigun, though it may be a little too comic and a little to actiony for your taste. (There is a core of gravitas to the protagonist, but he covers it up with humor and self-deprecation, as anime protagonists tend to do.)
I also think you would enjoy Serial Experiments Lain, which is a completely different creature altogether, but very well done, IMHO. Kind of a mind-fuck, excuse my French, but it’s relatively short so not that much of a time investment even if you don’t prove to like it.
No Full Metal Panic fans? It wasn’t fantastic, but it was good fun, and Fumoffu! is hilarious.
Metropolis was very well done, personally.
I’ll echo El-Hazard, though I would recommend scrapping the third one.
I like a lot of the anime already mentioned, but I also like those set in middle/high school, presumably aimed at kids of that age, but with enough to keep adults interested. These range from the screwball comedies like Love Hina (Keitaro Urashima runs a boarding house full of high-school girls, one of who he may or may not be in love with) and Happy Lesson (Chitose Hitose is an orphan adopted by 5 young female teachers from his high school, all of who are crazy in their own way, but none of them as crazy as Kanna, who has changed her plans of world domination to attempts to capture Chitose). Azumanga Daiyo is fun in its way, too.
At another end of the spectrum are the more serious ones like Fruits Basket (saying that this is about the Chinese zodiac plus thecat who got left out doesn’t do it justice) and Figure 17 (which is in part an action story involving extra-terrestrials saving Hokkaido from an alien life form, but which is more interesting as the story of a lonely middle-school girl who suddenly acquires a twin sister, and learns a bit about life from this extraterrestrial twin).
In between are such examples as Kare Kano (or His and Her Circumstance) and Oh! My Goddess (or Ah! My Goddess) – the latter being technically out of scope, since Morisato Keiichi is a college student with three Norse goddess (literally) room-mates, but it still has the feel of a high-school comedy.
I have to second (third? Whatever) Samurai Champloo, which is probably one of the best animes no one watches. I’m not an anime fan, either, but this one solidly makes my #2 Favorite TV Show Ever, right behind HBO’s OZ.
One thing that confuses people about SC is that it’s not your typical ‘magical princess fights evil wizard with help of her quirky and lovable friends’ type of anime. Rather, it’s an intensely personal story about three people: Fuu, a cute but unlucky waitress; Jin, a disgraced samurai; and Mugen, a rough-and-tumble criminal. Together they embark on a road-trip across medieval Japan, running into adventures big and small along the way. There’s no all-powerful villain, only villains of circumstance. Fuu and company complain about being hungry and tired, and every episode is as much a battle for survival as a battle against the forces of evil. Don’t go into the show with preconceived notions; despite his looks, Jin is hardly some pure-hearted hero, Mugen is not the dumb sidekick, and Fuu is not the delicate heroine whose heart they compete for. The heart of the show is the slow building friendship between the three core characters, and how they learn to relate to one another. Have a little patience, and I think you’ll find SC is a deeply rewarding experience.
This is just a tiny bit higher than you’re aiming (these are college kids), but I expect that you will love Honey and Clover. Just trust me on this one.
Nitpick: FMA occurs around 1910 in a European inspired country. Damn good anime, but its nearing the end of its run, so if you were to tune in to the show right now you’d be totally lost. DVDs are coming out, but they are overpriced IMHO.
Samurai Champloo is awesome and worth a look. There’s an over-arcing plot, but you can hop right in. Its’ odd like that.
Rurouni Kenshin is great if you can find it, particularly the second season. Again there are DVDs, but the last time I checked (three years back) they were really expensive.
I keep having to recommend Master Keaton just because it’s that frickin’ awesome. It’s about an archeologist, and it’s very low key and down to earth There was a thread around here a few weeks ago with great recommendations. We’ve been loving R.O.D. which I put on the netflix queue thanks to that thread, so you might want to search for that thread too.
I’ve also been enjoying Saiyuki, which is a somewhat subversive version of the legend of a priest travelling to India to bring scriptures back to China with three demon companions. Even the action sequences are punctuated with random philosophical musings. I’m biased due to growing up with the 70s Japanese live-action TV series based on the same legend though.
Rurouni Kenshin is a mixed bag -there are OVAs that are way, way darker but also more artistically impressive than the TV series.
Irresponsible Captain Tylor is great fun, very much on the light side of things though.
I always liked the more adult side of things, so a few from that side of the world:
The Hakkenden - A legend of ancient Japan and eight warrior “brothers” trying to become a family in war-torn Japan. Very good, very confusing.
Key: The Metal Idol - The “creation” of a roboticist has to travel to Tokyo and gather the spiritual power of 30,000 people in order to transform herself into a human, or she will die. Very good, still confusing.
Neon Genesis: Evangelion - The Earth has been attacked by giant entities, and the humans are forced to rely on children to pilot ungodly monsters in a war of inner-turmoil. (How’s that for a back of the box description.) Very good, even more confusing.
Akira - Normal people, with godlike powers and trying to deal with it while the rest of the world tries to reign them in and manipulate them. Very good.
Jin-Roh - A tale of a man who was born a killer. Mmmm.
Cowboy Bebop - A group of random misfits get into adventures, but are sucked into their past. Very good.
Niea Under Seven - Slow, quiet series about a couple of girls not really doing much but living slowly. Lurve.
Patlabor the First Movie - A group of police tries to track down and stop a man from killing millions of people. Quite Good.
Memories - Three shorts going from best to worst, but all are good. Nothing to dislike here, much to like quite a lot.
Eatman '98 - Hmm…what Trigun was ripping off. (Hey stop throwing things at me!)
Perfect Blue - A pop singer girl loses her sanity as a stalker invades her life. Very interesting.
Vampire Hunter D (New Movie) - A vampire hunter is hired to track down and return the daughter of a rich man. Much better than the description sounds like. Really more about the visuals and direction than the story.
Now and Then, Here and There - 
Grave of the Fireflies -
Personally I really like Revolutionary Girl Utena but probably best to ignore that one for now.
Princess Mononoke - I heard ten seconds of the dubbed version and had to flee, screaming. Watch it subtitled.
And…I wish I had my LDs with me so I could plop down another ten good ones or so.
<nitpick on>
Actually, compared to the bad old days (or is that BAD OLD DAYS [sup]TM[/sup]?) when one paid $39.95 for a single OVA of Bubblegum Crisis, and was glad to have legal, and understandable anime available, the prices being asked for FMA, or any other anime are considerably more reasonable. That price was about a buck a minute of entertainment.
At this point the problem isn’t greedy companies or anything of the like. It’s just that while anime is far more mainstream than it had been it’s still effectively a niche market, with the same economies of scale that keep, say, the DVD collections of Firefly more highly priced than the collections of Friends.
If you can’t afford the price, that’s one thing. But don’t think that the DVDs are overpirced when there’s been a steady price revolution over the years. And recognize that until the market grows to the next size increment market forces are going to keep DVD prices at approximately this same level for the next few years.
</hijack off>
Oh, on preview: Yes, Tylor is great fun. Is he that good, or is he that lucky?
The answer of course being: Yes. It’s one or the other.
It always makes me sad to see that I’m the only Kino’s Journey fan here.
At least I can second some of the other ones:
Serial Experiments Lain is a great show, even though I haven’t seen all of it yet. It was made by some of the same people who made Kino’s Journey, but it’s much different. Much more bleak.
I believe some of the people who worked on that also worked on Boogiepop Phantom. Although the title seems upbeat, it’s actually very creepy and dark. Like Lain, it’s very hard to understand, but it’s still great.
Trigun’s an excellent show if you can put up with some silliness and seriously ugly minor villians. It does have some serious themes though. One of the best and most important parts of the show is the protagonist’s refusal to kill.
Macross Plus is a great sci-fi miniseries.