First,the ones already mentioned that I second:
[sblock]Record of Lodoss War - OVA and TV series are both great, though have (explained, if you do a search on it) continuity issues. Avoid Legend of Crystannia like the plague!
Bastard!! - "There's only one god, and his name is Dark Schneider!" That's the main character, talking about himself. What more do you need to know?

Bubblegum Crisis
Tank Police
Cowboy Bebop - Haven't seen the movie, unfortunately, but the series is so good I'm going to just assume the movie is, too, and recommend it as well.
Trigun - It's almost like two shows. The first half is light-hearted and humor-laden, the second half is deadly serious. You could do a class on Judeo-Christian philosophy using just this series, in addition to the humor and action aspects.
Anything Gundam - Just be aware while most are serious narratives on war, there are some entries in the series put in for humor, like SD Gundam.
Ninja Scroll - Great story and action, with some drama and romance thrown in, too. The fighting done by the main character is pretty realistic, too. No superhuman powers, just skill and craftiness. Like keeping his sword on a string tied to his belt, if it gets disarmed.
"Gankutsuou: The Count of Monte Cristo" - Thank you to the person who posted this, I was trying to remember the name. Saw the first episode, it had little action, but lots of cerebral suspense.
[/sblock]
Dragon Half - Demented, sick fun. Only two episodes, it's incomplete, unfortunately. At my college, it was shown first each year as an "initiation" -- if your mind doesn't explode watching this, you can handle just about anything anime offers (shy of tentacle hentai).
http://en.wikipedia.org/wiki/Dragon_Half
Excel Saga - Similar genre to Dragon Half, this strives to parody not just other anime, but
everything, even itself. It has theme episodes, like a space invasion by cute but deadly furries, an "audience booster" where none of the male characters were allowed to be shown on screen, etc... It features a secondary character that exists mostly to undo the death of the main character, typically brought about by her own incredible stupidity. One of the secondary characters "speaks" entirely in subtitles, and so on. The scariest part is that despite all the randomness, all the events congeal together to form a coherent plot at the end.
http://en.wikipedia.org/wiki/Excel_Saga
Martian Successor Nadesico - Another great parody anime, this one on a spaceship. Of course, the best part is the fictitious "Gekiganger 3" anime (a parody of early giant robot anime) that the crew all grows to love. In the "review episode," they actually show the Gekiganger cast watching clips of Nadesico and saying that it's
their favorite show!
Martian Successor Nadesico - Wikipedia, the free encyclopedia
Ronin Warriors / Yoroiden Samurai Troopers - My favorite anime, first one I ever saw. Late '80's "magical boy" (think sorta like sailor moon) sentai team (similar to power rangers) that can summon mystical armor with special powers and finishing move type attacks that must battle the evil dynasty and its ruler, Talpa. The dynasty is another world that literally feeds off of the fear and anger of humanity. Talpa tried to conquer the mortal world 1000 years ago, only to be repulsed by a monk known as the "Ancient One" and now seeks his vengeance. Kinda cliche, but also lots of fun, especially if watched with the English dub and its so-bad-it's-awesome lines. The best part, however, is the villains, who present amazingly terrifying and grand entrances, have great "evil laughs," actually use wits to outfox the heroes on numerous occasions, and most amusingly, openly despise each other.
Ronin Warriors - Wikipedia, the free encyclopedia
Golden Boy - It's usually grouped as "Romantic comedy." Heh. This is an amazing anime (I hear the manga's better) OVA about Kintaro Oe, a freeter, a free spirit who takes temporary jobs. He's a human enigma: having taken all the classes needed to graduate law school, only to roam Japan on his bike taking temp work; a serial pervert who struggles to "keep it in his pants," yet also a gentleman with a genuine empathy for others' emotions; acting much like a dunce and rube, only to prove to be a very fast learner and disturbingly wise and prescient. But mostly, it's loads of perverted humor. One of the major running gags is his "toilet fetish" -- I won't even try to explain it, I'll just say nothing gross is displayed, it's used for humor, since the girl he's after usually walks in on him.
Golden Boy (series - Wikipedia, the free encyclopedia)
El Hazard - Yet ANOTHER fantasy parody/humor anime! I've only seen The Magnificent World, but I think most of the others have gotten good reviews. It has a megalomaniac villain and a main character that mostly just ignores him, only serving to further antagonize said villain. It gives the main characters super powers upon entering the fantasy world, the most funny being the nicotene-addicted gym teacher's, which gives him superhuman strength and skill in combat...but only if he's been without cigarettes for the past few hours. It also has cat armor!
http://en.wikipedia.org/wiki/El_Hazard
Burn Up: These OVAs feature lots of "fan service" -- skirts, bras, panties, and so on. I haven't seen the original, just W and Excess, both are worth watching, but especially the latter. Burn Up W mixes bloody action and some tragic moments with pervertedness and only some humor, making for a rather awkward result. Burn Up Excess, on the other hand, is more lighthearted and has tons more humor, integrating it well with the adult visuals and themes. There's an optional "jiggle counter" that does exactly what it sounds like, recurring transvestite burglars who seek "Moroccan sex changes," anatomically correct battle robots, and more! It has loads of comedy and eye candy, as well as decent action scenes, but also has a much better woven plot than W, all coming together in the last two episodes splendidly. If it helps push you to try it out, I convinced my fiance, who fiercely despises animated T&A and too often questions why I watch so much of it (clearly, I'm just messed up), to try watching it. Not only did she love Excess, we watched all 13 episodes in a single day. She normally can't watch more than 3-4 half hour episodes of anything in a day, so that was pretty incredible. I have not seen Burn Up Scramble (newest in the series), so no comment.
http://en.wikipedia.org/wiki/Burn_Up_Excess
I don't particularly like Slayers (music from it rocks, though), but a lot of folks do, and it's a parody of the fantasy genre, so worth noting.
I don't really read manga, so no recommendations there. Finally, this thread's awesome! I'm learning about a whole bunch of great series through it.