It pretty much makes sense regardless of what order you do the stories. I started with Zidane and then Tidus and left the most difficult stories for last. That worked for me. Some of the characters are travelling together and so their stories are linked but I didn't find my jumpy order messing with that at all.