New stuff:
Mushi-Shi: A refreshing eastern (as opposed to pseudo-western) anime focusing on a traveler named Ginko who specializes in treating afflictions caused by Mushi--small, usually invisible organisms unique to each area that normally keep to themselves.
Code Geass: An alternate universe where America didn't form, and Britain (Brittania) basically took over the world, including Japan. Forcing the Japanese to relinquish their national identity, they rename the country Area 11 and force the Japanese to call themselves "elevens." One of the princes of Brittania's mother is murdered and he feels the King did nothing, or might have even caused it. So he swears to destroy Brittania, and through his military genius, manipulates the Elevens/Japanese into fighting his war. Mecha that doesn't focus on the mechs. Excellent series.
Claymore: Similar to Berserk, a "dark fantasy" in which demons roam the Earth, taking the form of humans, and eventually eating them. When a city is attacked by the yoma/demons, if they have enough money, they call upon a certain organization that sends a Claymore--a female warrior in shining armor with an enormous claymore to dispatch the demon. The story focuses on one such Claymore, Clare, and a boy she saved. Excellent series, until the end which derivates from the manga.
Le Chevalier d'Eon: An alternate history about the numerous rebellions, plots of treason in pre-industrial France. An entertaining, beautiful anime that is rather convoluted at the end but is a nice ride overall.
Older stuff:
Last Exile: One of my favorite animes, period. This story is about two warring nations, battling over territory in an unhospitable world without much clean water or farmable land. Their efforts are normally regulated by a neutral third party, but due to the deteriorating status of one of the countries, they make a deal with the third party to break the rules of war and gain an unfair advantage. The story focues on two neutral mail delivery workers and how they get caught up in the war after delivering a message to the flagship of the fleet attacked unfairly by the desperate-other-power.
Hunter x Hunter: A story about a boy living with his aunt, thinking his parents had died when he was born--who discovers his father isn't dead afterall, and sets out on an adventure to find his father, join the ranks of his father's colleagues as a Hunter--a very diverse profession that grants one superior status to almost any other, allows access to areas banned to many, and numerous other perks. This story starts off slowly, but really takes off after it starts focusing on another character's story of revenge.
Hellsing: A story of an insanely powerful vampire working for an organization that hunts vampires--he does so for his own purposes. Don't want to spoil any more than that.