As a big fan of the StarCraft franchise, Sarah Kerrigan or Artanis would be quite interesting to see. Kerrigan especially I think would fit well into the Mortal Kombat style as she's extremely aggressive, violent, and can have quite the interesting move set, specials, and finishers.
She's also over-the-top enough where her taking on the characters in the franchise wouldn't be a stretch.