Another vote for
Twelve Kingdoms. It is one of the classic anime TV series and exactly what you are looking for. It starts slowly but becomes really compelling around episode six.
I'll also suggest
Dennou Coil. Although the main characters largely remain in the real world and dabble in the virtual world, eventually they have to venture into the virtual world to resolve their pasts.
In
Noein two parallel universes are engaged in a conflict that threatens to involve the earth. In true anime fashion, the crux of the conflict is a twelve-year-old girl living in Hokkaido. She travels to both universes over the course of the story. The rather atrocious English dub is streamed at
YouTube.
In
Mahou Shoujotai Arusu, young "Alice" (Arusu) falls into a magical world. While she wants everyone to use magic for good purposes, in the magical world darker forces have a different purpose in mind. (This show is on the verge of being entirely out-of-print. Last I looked there were a few copies at
Amazon.)
The "other world" in
Ikeko Meiro no Croisee is 19th century Paris, but it might as well be Mars to 16-year-old Yune. They eat such strange things there like
cheese. Another fish-out-of-water show featuring a Japanese character in Europe is
Ristorante Paradiso, though the young women is in her early twenties.