Yeah, I've seen Cowboy Bebob, and also Trigun.
If you're having trouble, I'll just say I'm interested in fantastic new places and interesting cultures. It could be fantasy or sci-fi, but I don't just want to see Earth in the past, present, or future with maybe a few fantastic bits thrown in. If it's sci-fi, I don't want to just see people faffing about in space blowing each other up. I'm interested in exploring, even if it's the interior of a suitable spacious ship. Even if it's stuff the characters have seen before, as long as it's new to me, I'll like it.
Kino's Journey or Mushishi are both fantasy.
As long as all the fantastic bits aren't hidden behind some sort of masquerade or something so that common people don't know about, it's probably okay. Although that might be okay if the base society is sufficiently different from our own.
Kino's Journey is pretty much as it sounds. Kino goes around and explores places. Admittedly, it's not very high on the fantasy scale, but the places she visits are intriguing.
Mushishi is heavily fantastic. The world is pretty much engulfed with mushi, a natural and pure entity with supernatural abilities. The notable thing is the way the show handles these mushi though. Their supernatural abilities aren't portrayed in a monstrous kind of way like in most other shows, but in a natural and "that's just how the world is" sort of way.
The best way I could describe it is that in most shows, a monster would be treated like, "Oh no, it's a monster that eats eyeballs, and it ate this poor young boy's eyes! We need to kill it!"
In Mushishi, it would be like, "This mushi settles in the eyes of creatures and consumes light. The mushi will move out of your son's eyes if he wears these sunglasses. This area has an usual amount of these mushi, because the crystalline structure of these caves scatter and reflect light in a way appealing to these mushi." Or something like that.
I do a terrible job describing it. It's an incredible show though.