Mmph. This represents the boiled-down overlap of two much longer lists ("good anime" and "anime not primarily set in modern Japan or a para-Japanese world"). I'm presenting these in alphabetical order, and with a warning that I suck at descriptions (and that the name spellings I'm most familiar with may not match those of the Wikipedia articles I've linked). Most of these shows have adult protagonists, so there's a notable shortage of scantily-clad schoolgirls ;P Also, they're mostly older series.
Berserk: Dark, violent and often rather gory fantasy series about a mercenary soldier who gets embroiled in seamy politics and evil magic. I first saw this fansubbed around the time Cowboy Bebop was first released in English, and it wasn't new then, so don't expect the visual quality of a modern show. Be warned that the manga was unfinished at the time it was produced (I'm not sure if they've hit the end even now), so a lot of threads are left dangling. Do not watch in the presence of children--in addition to the violence, it deals (albeit not graphically) with child abuse and other forms of nastiness.
Crest of the Stars: Distant future hard-SF series, kind of hard to describe. We follow the adventures of an ordinary teenaged boy who has, due to a quirk of interstellar politics, become a minor noble in an empire ruled by genetically manipulated not-quite-humans, as he begins a required term of military service with these culturally different people and befriends a young woman closely related to their empress. Slow-paced. Adapted from a novel. There are a couple of sequels if you like this one.
Escaflowne (the TV series, not the movie): This one does begin at a Japanese high school, but if you can get past the first episode, it moves onward and upward. Um, the short version: a Japanese teenager is transported to a world populated by beastmen, knights, dragons, giant robots, and other weirdness, and gets tangled up in a war. No summary I could fit in one paragraph could possibly do this show justice--it's fast-paced, tightly plotted, and the characters are brilliantly portrayed. The music was composed by Yoko Kanno, who also wrote the score for Wolf's Rain. A classic.
Nausicaa of the Valley of the Wind: One of Miyazaki's earliest films, and I would go so far as to say that it's also his best. In a future where most of the world has been covered by a poisonous jungle, one young woman fights to save the valley that is her home from destruction.
Pandora Hearts: Take Alice in Wonderland, reflect it in a distorting mirror in a haunted funhouse, fold in a conspiracy of assassins, and dump the whole thing into a fantasy setting sprinkled with a soupçon of Time Crash, and you might get something like this show. In a nation whose capital was destroyed decades ago by a mysterious disaster, young nobleman Oz Besarius is about to come of age--except that the ceremony that would have marked this occasion is interrupted, and Oz gets thrown into a supernatural prison known as the Abyss for the crime of simply existing. His only hope of escape is to form a dangerous contract with one of the peculiar beings living there, the Chains...and when he does finally get out, years have passed in the outside world over a period that seemed only days long to him. Now Oz must figure out why his existence is dangerous, and what the Chain he contracted with really is (not to mention exactly what happened to the capital)... Unfortunately, the manga is (again) still running, so the story stops in the middle. I'm still hoping for another season.
Pumpkin Scissors: A quirky show that follows a military unit made up of misfits as they attempt to clean up the mess left behind by a major war, while at the same time dealing with class conflict and the results of some secret military research. Better than I've made it sound, but it also suffers from Unfinished Manga Disease.
Spice and Wolf: When Lawrence the wandering trader visited the village of Pasloe during their harvest festival, he did
not expect to find the local harvest goddess/nature spirit lying naked in his wagon the next morning! Her name is Horo the Wise Wolf, she wants to return to her nearly forgotten home in the forests of the north, and she figures that hitching a ride with Lawrence might get her there. The result is a slow-paced road trip series that combines a not-quite-romance between two adults with medieval economics and the politics of trade.
The Twelve Kingdoms: This one also begins at a Japanese high school, but doesn't stay there for long. Youko's everyday life is suddenly interrupted by an attacking monster and a mysterious stranger who hails her as his queen. Confused and disturbed, she allows said stranger to transport her to the land he claims is her kingdom, but once they arrive there, the two of them are separated almost immediately. Youko is left to fight her way to the throne of Kei on an island where children literally grow on trees... This one is worth it for the quirky world-building alone (the culture is basically ancient China with magic and some really peculiar add-ons). Adapted from a series of light novels.
Utawarerumono: Fantasy. The main character wakes up one morning with no memory and wearing a mask that he's unable to remove, but before he can find out exactly who he is, he makes the mistake of saving an ordinary villager from a local petty noble...and things snowball so wildly from there that he ends up leading a rebel army and conquering the country, which in turn complicates his search for his identity immensely.
I could probably come up with a dozen more good-but-not-great fantasy series in a similar vein. Also, I didn't include a number of favourites of mine that either are mostly set in Japan, or are just plain peculiar. Oh, and I second the recommendations of Trigun, Last Exile, and Monster.
Edit: @FW: Yes, that really is the opening of Paranoia Agent. Yes, it's bizarre. Then again, so is the show.
