My kind of ultimate reward/secret would be gained by winning through arcade mode with every character on hard. After completing this you receive a large message saying,

"You have opened the portal where ultimate evil awaits - choose your greatest warrior and kill all opponents to get to it."

The message actually means fight through arcade mode with anyone once more and commit fatalities on every stage, ie. no "Hari Kiris" against you as well.

When you have completed this task successfully you are presented with a brilliant cut-scene of your character walking through the secret portal (there may be a choice of 2, explained at the end).

Here is where you get to a secret arena and the chance to gain 2 more warriors on your playable characters list. My example is next :

CUT SCENE - You step out the other side of the portal to the boos of thousands in a large stadium. You look to your feet and the ground is sandy with blood soaked into it everywhere. You look around and can't believe the vastness of the arena, you see loaves of bread being hurled at you by the crowd and see the guards at the far end opening a large steel gate. Boos turn to roars as a Roman Gladiator emerges, walking defiantly toward you, bloodied sword held at his side. You immediately realise you have stepped into the past and appeared inside the Colliseum of Rome. The Gladiator turns toward the emporer and with the crowd yells as one, "Hail Caesar." You turn and look at the Emporer and immediately see it is SHANG TSUNG who has the whole crowd hypnotised under his spell. You notice him then draw the soul of a dead Gladiator on the ground a distance away and then look back to you laughing loudly, his voice echoing around the Arena. ENDS CUT SCENE.

Now you fight this Gladiator, who has been granted powers (special moves) by Shang Tsung. Without meaning to take too much from the movie, "Gladiator" it would be perfect in the MK universe to have the starving, ferocious Tigers on the chains, springing from the ground in certain areas when you move too close, taking a swipe at you or your opponent.

If you win, you will hear the crowd chant, "Kill, Kill" or "Live, Live" and must look at Shang Tsung for the thumb up or thumb down and act accordingly (The swaying victim would be swaying just a little longer than the normal MK battle).

If you obey Shang Tsung you have gained this Gladiator (Totally authentic Gladiator appearance by the way) as a new character at the select screen. His story is obviously a champion real-life Gladiator, abducted by Shang Tsung from the past to fight for the forces of evil or similar.

If you disobey Shang Tsung he banishes you back through the portal and you get nobody except now you get to fight him (Tsung) in the Colliseum if you qualify again (same way as before) with same warrior. Beat him (Tsung) and he joins the playable list. You can still obtain the new Gladiator Warrior with another fighter if you haven't yet.

Sorry it's long, got a little carried away.

For the other portal idea I was thinking of Quan Chi being found in a futuristic setting.