They should probably do a few things to the game, first:
1.) Focus on substance, not style. Sure, the squeaky clean world was cool but I wish they had paid as much attention on actual gameplay.
2.) Ditch the [insert unoffensive word for "illogical" here] plot. Take the Red Steel approach and completely abandon the old plot. Sure, you'll get some flak for that but not as much as if you tried to elaborate on the confusing-ass story!
3.) Add a free roam mode. Sometimes we just want to free our minds and relax... isn't that what parkour's all about?
4.) A longer production period. EA rushed out the first one, give them a bit more time and I bet they can churn out something truly superb.
5.) No console exclusive DLC.
6.) Multiplayer, I don't want to just run around a "ghost" of someone, I want to play dirty and sneak in a few punches to slow them down.
6a.) Multiplayer modes like Capture the Flag, Deathmatch and stuff. No reason why they CAN'T include these.
7.) A more urban, less alien environment. Because it's so much cooler running around in a place like New York than it is in some uncolored building models.
TL;DR version:
Longer production, a "not stupid" plot, free roam, no exclusive DLC, multiplayer and urban environments.