FF4 was the first one to have a cohesive story (and one that is still very good, IMO), but FF6 is just the pinnacle of the series as far as I'm concerned. Admittedly, I never played 9, and never finished 8.
Also, even though the protagonists were downright annoying, I think FFX gets too much flak. The thing is, the FF series got so famous for its engaging storylines, until it focused so much on making them more complex that they stopped... making sense. FFX (and even FFVII) have very deep stories, but some of the plot points in the stories (which I won't mention in particular because of spoilers) are just plain ridiculous.