Yes, yes, YES! I had no idea a thread was already started on this.
I actually attempted this a while back. Not a proper TAS, but something I did for fun... it got deleted, unfortunately.
I used Elfin and Dick in the Japanese version. IIRC, the English version makes it hard to skip the dialogue; you can't just hold down the start button to dismiss the text. The inclusion of the spider-bots might not be a good thing, in terms of TASing. The hit detection on those things is a little clumsy compared to the "Squash" enemies that replaced them in the English versions.
Elfin's running knee-thrust seems like a good complement to Dick's half-circle throw... You probably wouldn't want to use Elfin's HC-throw, as it tends to launch the enemy out of the screen.
I think Orbot might be worth testing, as he (it?) has those "Go!" dash attacks (for the sake of movement), and generally dishes it out like a badass, alternating between his x-charge and grapples. It could be that he would be useful in some levels, but not others. Fortunately, characters are reselected at the start of every level, so that's another demension to the strategy; another reason to TAS the hell out of this game.
For information's sake, Orbot and Norton are enabled by pressing and holding L+R+A (the shoulder buttons, not the D-pad) during the opening logos, up until the title screen.
As for routes... I don't know much offhand, but I'm sure Ozymandias would be a smart choice- all those pits everywhere, just asking for enemies to be tossed in. Snake Pliskin would be a bad choice. Long and brutal, and the bosses have uninterruptable attacks, which might be difficult to avoid.
Taking the underground path to the Crazy Horse and letting it crash is probably unworkable compared to the Airport route... those Thirdons are laggy as hell.
Damn pirates.
By and large, the routes are small choices, made between a lab that has spike pits, and an identical lab with electrical fields. There's also the occasional scientist hidden here and there- it's probably worth including them in the path if it means avoiding enemies. -And that's a big if.
The big question probably lies in choosing which to fight first: Connor or Jesse.
Onto the miscellany...
Invulnerability is tricky. You can be shot by orbots while in grapples, IIRC. Flynn's A-attack, however, is less vulnerable. I think only Yamaoka's horridly cheap throw attacks can take priority over the A-attack, but I'm not entirely certain.
One more thing I would test: have player 2 join in after the action has started. I think it'll save a couple frames from that first selection screen.
Dick/Flynn's Super Saiyan mode can be invoked repeatedly- he just needs to recover some health and then get his ass handed to him again- an obvious time waster, which is why I think it might be worthwhile to keep friendly fire enabled. To have Elfin slap Dick around during the brief pauses here and there (waiting for scrolling, etc) could have him ready to transform for the boss fight.
The bosses, however, I found to be easiest disposed of using infinite combos... Maybe not quickest, however. It's possible to grapple and let go with the X button cheer thing in order to buy a few frames, thus preventing a knockdown blow.
That X-cheer might be useful for AI manipulation. You never know.
I'm not sure when, if ever, one would use the X+A attacks. They're very time consuming, and don't do that much damage compared to straight fighting... I guess Kira and Onido?
...Any takers?