Story stays the same overall, yet some details are modified, some dialogues (mainly concerning Tifa and Aerith) added/changed.

New materias/spells:
-no more HP/MP pluses, replaced by def+/spirit+.
-Some materias have a slight change in stats bonuses/maluses. For example
Barrier/Heal does not drop your attack/def/HP and enhance your
magic/Mdef/MP since they does not use the magic stat (you're thus
encouraged to give them to other than magic users).
-No more Exit, Poison, Mystify and Seal materia : most alterations can be now inflicted
by enemy skills. There still are the "Transform" & "Time" materias.
-Cure and Regen are now separate materias.
-Some materia location/obtention changes, including early Enemy Away materia
if you want to avoid annoying battles. Be careful to not abuse it
though.
-2-Cut and 4-Cut are separate materias. Same goes for Slash-all and Flash.
-No more contain but now Ice4, Fire4, Quake4 and Aero4 spells. Contain is
replaced by "Mako" materia with 2 new spells (PU239 and Nuke).
-Shield grants you a 50% boost in def/Mdef in addition of the statut.
-Wind, Water, Light (Holy spells) materias added.
-No Poisona spell : the Heal materia now contains White Wind (Laundry).
-Invocations now ignore defense (except for KoTR) and many cause stats drops (from
slight to consequent) in order to rise a bit their usefulness.

New enemy skills : nearly all enemy skills are changed or replaced in order to be useful yet not game breakers.
-Some enemy skills ignore defense (but NOT pandora's box which works differently).
-Some physical enemy skills with different physical element (shoot, weight, shout) some monsters/bosses may be weak against.
-Some status inducing enemy skills (even Sadness/Fury, and many bosses can be afflicted by Fury...)
-Some stats boosting ones (i.e : big guard now rises your def/Mdef by 20% and
gives you Death Force instead of granting you barrier/MBarrier/Haste)


Character "roles" :
Even if I tried to keep the original spirit (you can equip anything to anyone),
character's weapons give them some specific boosts (Vitality/Spirit for
Barret, Strength for Tifa, Magic/Spirit for Aerith, ect.). Slight change
for stats curves, too.
Some weapons diverge from the "normal" rule and may give some other boost (i.e. the umbrella gives strength/vitality
to Aerith). Final weapons have some shuffle (i.e : now Yuffi's
conformer -now materialist- depends on materias)
and their localisation are changed, except for Vincent one. You cannot obtain them
until disk 3 (except for Cid's) but they're not difficult to obtain...
Like NT you can obtain the Masamune, though only Cloud can equip it (can
be considered his true final weapon) and the mean is different.

Limits Breaks:
Most stays the same, except for Mindblow (Magical inflict Confu) and Planet Breath (Regen/Wall).

Armor/accessory changes :
Changes were made to armor/accessory, generally to protect from an element or status. Some also protects from physical elements.

battle changes :
-Bosses remain but their stats, attacks, AI, weaknesses are changed.
Bosses/minibosses added. All the bosses are more difficult than OG, from
barely (Guard Scorpion, air Buster), to very, very frankly (The
Jenovas, Hojo, etc.).
-Most normal enemies location are changed to feel more "logical", for example in the sewers you do not encounter
Sahagins/Cesars, they are now on the Kalm/Chocobo farm beaches. Or now
Gargoyles are encountered at the Temple of the Ancients.
As a consequence, many have now different stats, attacks and sometimes AI. New
enemies sprites based on NT 1.5 added, too.
More "fair" rewards, difficult enemies grants more xp/ap and good items whereas weak ones stays the same.
-Special Battle in GS is changed, quite difficult but with 3 characters now. The reward worths it, though.