My favorite parts of the story were the bits that overlapped with Final Fantasy VII. There is only a little retconning going on, but overall you get the same general tale that you saw in Cloud's Kalm flashback and then that is expanded upon to create a 12 hour main questline or so. This means you hit up locales like the Shinra HQ, Nibelheim, Gongaga, etc. There are many parts in the story where you might find moving, and the FFVII bits are some major parts of that. Zack's interactions with Aeris are really nicely done in particular. Zack dragging Cloud along with him to Midgar is great, and I will just say the ending is spectacular. The last line of dialog in the game is fabulous (Nojima is good at this) and the music and visuals all combine to leave a very powerful lasting impression.
The good lasting impression is kind of necessary. I have a problem with is the original story. I'm going to be downright honest: I don't think it's very well told, or maybe I don't think the translation of the game is very good. Genesis is constantly quoting from LOVELESS, but at no point is it ever really explained what significance LOVELESS has for the FFVII world-- at first I thought it was just some trashy book of romance poems with a stage production in Midgar, but in reality it seems to be some kind of foundational text like the Iliad or the Odyssey. The lines from LOVELESS often seem needlessly complex and overly poetic; they frequently don't make any sense (often intentionally) and they get really confusing. Only after watching a lot of the cutscenes on Youtube did I go, "Oh, THAT'S what he was talking about." For much of the game I was waiting for that like unifying epiphany where it becomes explicitly clear how everything is related thematically, but I don't think it happens until far too late into the game.
Second, I'm not sure the tone and themes of the game really meld well with FFVII at all, or if they make sense individually. The whole thing with copies spawning from Genesis and Angeal, Angeal becoming basically a dog, Angeal fighting Zack and supporting him at the same time, Angeal basically possessing Lazard towards the end, it seems kind of strange. It's like the Sephiroth clones in FFVII, except these clones don't have some kind of Hojo experimentation to explain their existence. I guess it wouldn't be FFVII if the sci-fi wasn't nine hundred layers thick and poorly translated, but for a large portion of the game I just didn't know what was going on. Just when I thought that Genesis was a crazy wacko like Sephiroth who believed this book LOVELESS for no real reason other than he was a crazy wacko, the final boss battle reveals that there really IS a Goddess and she's displeased with him. But she still heals him in the end, so that was a little confusing.
I'd say the biggest problem I have with the original story is the relationship between Zack and Angeal. It's very confusing and frequently in a state of flux. Is it just that Angeal goes kind of crazy and then is able to see the error of his ways afterwards (and therefore he begins to support Zack?) What's up with him dying and then becoming a bird dog anyway-- how does that work? We see very clearly that he does die. At least with Genesis we don't really see his death the first time you fight him.
To complicate matters, I don't think the translation is well done. Conversations do not always flow naturally or well, and frequently a character will say something completely unprompted that you want explanation for that the other character won't even question. There's a few messy grammatical structures that kind of make you cringe when you hear them spoken (the voice acting is really good, I think. Aeris finally doesn't blow. Thanks Mena for getting it right on take 4). Furthermore, I don't think a lot of dialog really makes sense in English the way it is written. In the opening cutscene, they tell Zack to take it seriously or something before he jumps out of the helicopter and he responds with something that doesn't even really make sense. He says like "oh yeah!" or something retarded.
There is one point after the final boss' first form where the end of the story where Genesis is babbling garbage to Zack and Zack says, "So this whole time, you knew?" or something to that effect. I have literally know idea what Zack was talking about. There's a lot of lines like this too that were made very clear only after reading a summary or someone else filling in the missing bits. Later, Genesis tells Zack that his "dream" has been fulfilled, but you will only catch what the dream that has been fulfilled is if you pay close attention. The sentiment itself is really touching, though, once you figure it out.
With the frequent use of terms like "honor" and "pride," I thought I was listening to Shawn Elliott make fun of morons on message boards. It's just hokey.
I read a Crisis Core Wiki just before, though, and now it is actually all clear to me. I really like the story itself, I just think the delivery is more than a little hairy. I basically understand it as a quest by Genesis to stop his degradation, and along the way we learn how the three men (Genesis, Angeal, Sephiroth) give up their dreams and how Zack must hold on to his to hold on to his humanity. It's a really nice story. I don't think it's translated well or told clearly at all. That said, there are definite scenes that made sense and were emotionally moving-- mantears will happen. Get the hankerchiefs out.
It's entirely possible I just wasn't paying TOO close attention, but the whole relationship between Zack and Angeal and whether or not Angeal was actually dead (after friggin fighting Zack...) confused the hell out of me. There are too many vague or confusing lines in the story. This isn't Final Fantasy VII-- there isn't a TON of text and it's just as involved a story. The primary failing of the story is, IMO, the game's failure to establish LOVELESS as some sort of important document. I just thought Genesis was a fucking nutbag. And what's with Zack making his hair into like Goku's? Shiteous.
Like I said, there are definitely moments of clarity. The last line is one of them. Such a great last line. Reminds me of FFX a lot. The whole dialog before that though really threw me for a loop. I can't tell if Nojima is just crazy or if the translation is not as clear as it could be...why would Zack want wings? It would make more sense if he said he wanted to spend time in the lifestream with his friend Angeal or something. Angeal's hand coming out to pick him up...:'( :'(
There's some really neat symbolism at work too, like Genesis and the Banora Apples (apples being a very classic symbol of seduction and such). Somes you just feel like they are trying too hard...white vs. black wings. I think it's a pretty neat story overall that's really confusing. In that way, I guess it's pretty compatible with Final Fantasy VII. Great if you want to do a little legwork. After doing the legwork, I'm very satisfied with the story. They really should have put their top localization team on this. I don't think they did. :\ Can't blame them with PSP sales in the condition they're in.
So I'd basically sum up my thoughts by saying I'm very happy with the gameplay and, retrospectively, happy with the original story. I was really frustrated while playing it and if anyone else felt this way, please let me know. I don't think it's very clear at all, but I could just not have been paying close enough attention. I really feel like Genesis in particular is not a deep enough character with enough exposition to build a convincing relationship with Zack...I guess that's why you can be so easily confused by his position vis-a-vis Angeal/Sephiroth/Zack at any given moment.