I'm going to mention one thing that I think Square could have done much better with the story, since others have discussed the linearity and combat system. They try to make a three-act story into a game with a five-act structure and don't even really raise the dramatic question until 20-25 hours into the game.
Break the game down into its most basic story components: each character is established, they meet, muck around in Cocoon, eventually get booted out to Pulse, muck around in Pulse, come back to confront the big bad. So, in essence you have a few hours of exposition, about twenty hours of rising action and a small plateau, more exposition in which the dramatic question is raised, ten hours of more rising action, then a climax and resolution: five-act structure. When in reality all that game play in Cocoon is really just exposition, the dramatic question isn't even raised until just before the party goes to Pulse, then after ten hours of rising action the climax: three-act story. Plus they even had the gall to tack on an in medias res opening to a game in which the dramatic question isn't even raised until twenty-ish hours afterwards.
Not to mention the characters aren't in the least bit sympathetic until they get to Pulse and figure out they need to get over their shit and work together. Then they're arguably even worse considering the ever-permanent "POWER OF FRIENDSHIP! GANBATTE! *Japanese Fist Pump*" in chapters 12-15. Argh.
Anyhow, where Square could have done much better was to have the characters become l'Cie, and Anima gives the mission to assassinate Dysley. At that point the characters still loathe each other and get chased to ground by PSICOM, then half-assedly attempt to assassinate Dysley; wherein he reveals himself as Barthandelus and readily delivers a whopping case of whoop-ass with Exposition 2: Convoluted Plot Boogaloo, which raises the dramatic question. The party escapes to Pulse, having just gotten their asses handed to them in legendary fashion, bringing us into Act 2 in five hours, tops.
Now, Pulse was fantastic. Easily the best-conceived and well-written part of the game, almost made me feel slogging through the previous 20 hours of crap was worth it. Expand that f*cker to about 25 hours, and have all that character background establishment, mutual loathing and attempts to off each other there, followed by reconciliation and team coagulation. They fight Barthandelus again and whoop up and make their way back to Cocoon, bookending Act 2 and introducing the climax which could have decently followed the game's structure.