Storyline wasn't cliche like some other games we know. And music and art style was a welcomed suprise after both FF8 and FF7 darker and more serious atmosphere.
Er, the storyline to FF9 was pretty cliché. Right from the beginning it starts with some thiefs kidnapping a princess. I've heard that one too many times.

I'd also say I prefer darker games, like FF6 which I'm playing right now.

You could call FF7 and FF8 almost science fiction, while FF9 went back to the roots of fantasy again.
That's one thing about FF9 that I love, all the references to older FF games. XD I hadn't played them the first time I played FF9 but now that I've pretty much played all the older ones I get all the references in it.
