Anime is more accessible to get into these days since a lot of series have cheap boxsets now. Here are a few recommendations in various genres:
Fantasy
Escaflowne
If you like JRPGs, you should love this series. It's about a high school girl who gets transported to a fantasy world in the midst of a major war between kingdoms. It sounds pretty typical, but it's not. Great story, interesting characters, awesome action, and it all takes place in a captivating world. You can get the entire series for $30-$40 at Best Buy.
Princess Mononoke
This is a movie, but you should still check it out. In fact, I believe if you want to get into anime you should check out movies first since they are shorter, cheaper, and a lot of them destroy any series out there. This is a fantasy story about a cursed prince who gets caught in a war between humans and the spirits of a nature. A truly incredible film, one of my favorite movies ever, animated or not. You should watch EVERY film from Hayao Miyazaki since they range from very good to masterpieces. You cannot go wrong with him.
Action
Cowboy Bebop
Easily one of the most accessible anime out there. It's a mix of sci-fi, action, crime drama, etc. Everyone who has seen this show has more or less loved it. There really isn't much that I can say that hasn't been said before. You can buy the series for $40 at Best Buy.
Hellsing/Hellsing Ultimate
A show about vampire hunters, how can you go wrong? There's two shows, Hellsing and Hellsing Ultimate. Hellsing is a 13 episode series while Hellsing Ultimate is an OVA (original video animation, think of it as a direct to dvd series) that is still going on. The tv show is a good action show, but it also mixes it horror, suspense, and more character drama. Hellsing Ultimate is just a balls out gory wild crazy murder spree. They're both pretty different but I like them equally.
Sci-Fi
Ghost in the Shell: Stand Alone Complex
This is a well-rounded series that excels in a lot of areas. Exciting action, good cop show drama, some interesting philosophical mumbo jumbo, unique characters, and just in general good sci fi elements you'd expect from the genre. There are two seasons (the second one is called 2nd GiG) and I recommend both of them. The first season mostly focuses on the overall story arc and the society and culture of the world. The second season gives more attention to the characters. Both are great and worth checking out.
Neon Genesis Evangelion
Ah Eva, probably the most infamous anime series of all time. It's required watching for any anime fan though, and it still stands the test of time. A really fascinating series with now iconic characters. There are so many different boxsets for this, but I think the Platinum one is the cheapest, it should be around $60.
Drama
Haibane Renmei
This 13 episode drama is about a young girl who is reborn into a melancholic world where everyone looks like angels. A strange description, but it's a great character drama even though it's a bit slow. The boxset is around $50 I think.
Grave of the Fireflies
Another anime film many dub as a masterpiece, Grave of the Fireflies follows two children who try to survive in Japan during the closing days of World War II. Beautiful but heart-wrenching, it is a must-see film for anyone.
Adventure
Kino's Journey
This show follows a young traveler who chronicles different areas around the world. It's an episodic show and a story arc with the main character doesn't appear until the very end, but each new area has a slew of interesting characters and situations with some amusing lessons. Also, her motorcycle talks. A really wonderful show, it's about $30 for the entire show.
Trigun
I just kinda shoved this show in adventure. It's about a gunman who has supposedly massacred entire cities, but the truth is far more interesting. If you like westerns you'd like this. It also has a lot of sci-fi elements and character drama. I'm not sure if there's a cheap boxset for this.
Horror/Suspense
Paranoia Agent
People are randomly getting attacked by a kid with rollerblades wielding a baseball bat, but what is the connection? What is happening to this town? The show has a lot of pretty disturbing stuff, but it's fascinating with some realistic and well-developed characters. The director is Satoshi Kon, and the rest of his works are must sees as well.
Boogiepop Phantom
A strange pillar of light explodes from the middle of town, and the show follows random people who were affected. Similar to Paranoia Agent, it mixes strange supernatural horror with character drama. It's really interesting and stylistic, it's unlike any anime series.
Those are just a few recommendations. There's a lot of good anime out there, but there's also a lot of bad things. I recommend you try movies first and then move onto series. The good thing about anime is that there are so many unique and genre-innovating stories out there that you won't find anywhere else. The bad thing is that you might meet a guy who will not shut the hell up about Haruhi Suzimiya or whatever the hell her name is.
