For someone just getting into anime it's difficult to recommend a lot of shows. Many anime series start off very slow. Many times there simply is no explanation of events that happen until later - sometimes quite some time later, if at all. One of the reasons for this is that the Japanese are masters at vertical marketing. Many anime series or movies assume that you've read the novels/manga they're based on, so they don't feel there is anything to be gained by giving you a long explanations. They'll also adapt sections of said works.
Also be warned: Many but not all anime series, like a lot of other Asian cinema I've watched, do not obey 'Hollywood rules'. The good guy does not nessesarily win. The boy and girl do not nessesarily get together. Yes, you may watch five seasons of a show only to see them fail in the end, or part forever with melancholy looks. No-one has 'plot immunity' and that includes the star(s) of the show. You will also get used to ambiguous endings where you're just not sure what happened, if anything. If you hate romance in all it's forms, you'll hate something like 75% of all anime series because almost every series has, as its core emotional motivation, a love story.
Wikipedia is also your friend of friends when it comes to explaining various anime tropes like 'what is a harem show?' or 'what does a sweatdrop mean?'.
Fantasy
The Twelve Kingdoms - one of the best fantasy-themed shows there is. Remember what I said about an anime that starts slow? This one does. It also on the surface seems to have a heroine who hates her destiny, which is always somewhat irritating. She gets over it.
Scrapped Princess - One of the very few 'western-ish' fantasy shows you'll see.
Record of Lodoss War - I'll still recommend this.
Giant Robot
Where to start? OK, one of the first thing people will usually recommend is Gundam. Gundam illustrates another weird aspect of Japanese production: they will run a concept into the ground just like any American production but they do it in a strange way: they will produce infinite variations on the same theme. These variations might be alternate time lines, where characters look the same but act differently, the same events play out in different ways, etc. Gundam was the first and most successful of the 'realistic robot' series, so it still lives on today in dozens of variants.
What you'll want to look at are the compilation movies done from the TV series, which were re-edited, the creator took out a lot of the strange stuff the TV studio made him add in, etc etc.
Gundam Mobile Suit Movie I Special Editiion, Gundam Movie II and III, and Char's Counterattack should do it.
Ghost in the Shell, the movies and TV series. Don't let the horrible, horrible opening to the TV series fool you. It's done in wonderful animation, not crappy CGI.
Appleseed, any of the movies.
Witch Hunter Robin
Irresponsible Captain Tyler is one of the few comedy series I will recommend.
Planetes (not a typo) is a realistic space drama about the crew of a salvage/garbage divsion, cleaning up all the space junk left in orbit.
When They Cry and Red Garden are both very good examples of the Horror genre.
Shonen Onmyoji is a good supernatural series, however there are only three discs available from Netflix; Funimation picked up the rights to continue the series, but it's unknown when that'll happen. There are 26 episodes total.
