Having played this game when I was younger, and then replaying it a few years ago, I realize just how boring this game actually is. As far as a TAS goes, I know there's only so much to work with, but I believe that there's more you can do with this video.
Firstly, have you ever seen this video?
http://www.youtube.com/watch?v=2Bp4-_3DIPo&feature=fvw
It's a combo video of the first MK by the DarkTemplarz, who are well-known for their combo videos. I know this video show-cases the Arcade version of the game, but I believe some of these combos -- which by the way weren't really intended for this game -- can indeed be replicated in the Genesis version. Though I'm not sure how many.
Here's another video:
http://www.youtube.com/watch?v=dLn-JLmxI0A
This is a Genesis speedrun showing off combos and a few quirks with Raiden. A good example of an entertaining combo can be seen starting at 1:37. Now maybe it's just a character choice, but if such entertainment (ie. combo variety) isn't possible with Liu Kang, then perhaps another character?
And as far as versions go, the Genesis version is easily the best. Graphics aren't too much different, and although SNES has better technical sound quality, the music is clearer and catchy, whereas in my opinion, the SNES version just sounds like a jumbled mess.
I'll hold off voting for now, but I would strongly suggest at least checking out those videos and getting your opinion.