I disagree. Ghost in the Shell does get a bit carried away with the monologues at a couple points, but I really didn’t find it confusing. It’s an excellent piece of cyberpunk-style SF, and definitely my favorite anime.
If you like comedy I recommend the series Ranma ½ They also have quite a few movies if you’re looking for something longer.
I also found it very confusing, and slooooooow.
And I wanted to second **harmless’ ** suggestion of Ranma 1/2, or Maison Ikkoku for a sweet love story.
Yet another vote for Cowboy Bebop, and I’d also like to toss in a vote for Gundam: 08th MS Team. It’s a 12 episode OAV about a squad of soldiers fighting on Earth (the story runs more or less paralell to that of the Mobile Suit Gundam tv series from a while back) For the most part it’s a mecha show, although two of the characters do drive around in an armored vehicle of some sort.
Cowboy Bebop
Tokyo godfathers
Samurai Champloo
Big O
Bleach
I just finished watching the series(and the movie, between 22 and 23) and I can’t recommend Cowboy Bebop enough.
Every time I finish, I half think that there should have been another season and half think it was perfect the way it was.
Am I the only one in the world who wanted to set the Nausicaa DVD on fire after watching it because of the way the main character was handled? I found her treehuggin’ everybody-can-be-friends philosophy to be extremely heavy-handed, simplistic, and–and–yeah. Even trying to explain it makes my eye twitch and my hands itch for heavy blunt objects. 
Given **BluePitbull’s ** bent toward SF and comedy, here’s another vote for Trigun. (Vash! Vash the Stampede! The Human Typhoon!)
Ghost in the Shell and GITS: Innocence were both excellent SF animes that I didn’t have much trouble understanding. If you want confusing SF, go try Lain. Several years after the first two DVDs gave me a headache trying to grok them, I’m about to try it again.
Otto, you’re recommending Grave of the Fireflies to an anime newbie? That’s mean! 
I’ve heard someone say of it, “The best anime I’m never going to watch again.” He ain’t kidding when he says it’s a tear-jerker of the first water, kids.
If you happen to like Miyazaki, give Night on the Galactic Railroad a whirl, which has a similar feel. It’s about two young cats who take a night time trip on a magical celestial train, and is very nicely handled and can be thought provoking at times. It’s slow-paced, so if you’re looking for action or slapstick, this isn’t the one for you to rent.
Ooh, if you want funny and action, try Read or Die. It’s a short anime about attack librarian ninjas. I kid you not. Dead awesome. This one is on my list of Things To Buy.
Oh, you might take a look at some of the anime anthologies that they sell out there. Animatrix, which I think was mentioned before, is a good one, and another that I liked is called “Robot Carnival”, which, unfortunately, doesn’t seem to be available on DVD, only VHS. Each segment is from a different animator in a different style (my favorite part of Robot Carnival is the segment featuring a battle between two giant robots… in 1899. That’s right, coal-fired robots, baby!
Good show. Perhaps not a great choice though, as it hasn’t been dubbed yet.
As for Ghost in the Shell, I’d probably second the suggestion to avoid the movies. They’re good, but they do tend to drag, and I can see why people don’t like them. The series I’d suggest watching though–it’s also kinda slow at times, but overall I find it a much more enjoyable experience.
I also second the Read or Die nomination, though lizardling only linked to the OVA series. There’s a full series as well, which I haven’t seen yet. The OVA is only three eps and can be watched on its own.
Just to clear up any possible point of confusion–the original language for Vampire Hunter D is indeed Japanese. The original language for Vampire Hunter D: Bloodlust is English. The English for Bloodlust is not a dub.