+1 for making Vincent and Yuffie non-optional and part of the core story
Also,
-Leave the main plot the same, flaws and all. Adding new exposition, backstory, etc., would be fine.
-Aeris still dies
-Make Sephiroth harder. Or, have an optional "limiter off" mode for hardcore players. You should not kill the endboss with one Omnislash.
-Keep the good minigames. Snowboard, Chocobo racing, Mountain Battles, etc.
-Keep Barrett's swearing
-Keep Cid's swearing
-Some new or tweaked combat features, materia changes, etc. The Limit breaks could be made more interesting and less generic
...And the number one ultimate non-negotiable deal breaker for the remake:
-KEEP ALL THE OLD MUSIC. Every last song. Update it and make it better than midi quality, but no original shit. Use the Black Mage's version of the battle themes.