I am upset that nobody has brought up Escaflowne yet, SO I WILL!
This one is one that ran around the same time as Pokemon did (when it first aired), and I think it probably shouldn't have been on the same time slot because this show is not for kids--teens at the youngest! XD
It's a Girl-Gets-Sucked-To-Another-World story done right because the world she goes to is at WAR. It's a medieval fantasy with steam-punk mecha, a memorable cast of characters, and the atmosphere is to DIE for (made male choirs cool before Skyrim did). Some people get lost in Harry Potter, I get lost in Escaflowne.
Though, I have to warn you, the show was apparently supposed to go for two seasons, but only got one. So, they very obviously crammed a lot of stuff into the second half of the show to finish the story. Like, as soon as they go to a place called the Mystic Valley, you can say the show jumped the shark. Not that there isn't good stuff in the second half, but it just wasn't as solid as the first half. Also, the ending is complete bull. The end of the Escaflowne Abridged series is my head canon for what happened because the actual ending was so frustratingly dumb.
But the fact that I'm still recommending this series despite these big flaws should say a lot about my respect for it. I love how every time I watch it, I noticed new details--definitely a show to watch more than once. Also, they're apparently going to redub it soon, so that's something to look forward to. 
