Here are some stage fatalities I think could work in game.

Pit Bottom - Pick up your opponent and throw them on to the spikes. Similar to Shang's MK3 fatality.
Kahn's Coliseum - Roundhouse them into the background where one of those monsters swallows them whole.
Rooftop - uppercut them to the street, similar to the Pit 2
Soul Chamber - Knock them into the souls where they are torn apart.
Graveyard - Knock them into an empty grave or something and have zombies drag them down.
Goro's Lair - Push them into whatever monsters are there and have them be dragged into the dark with gruesome sound effects.

Desert- Roll them and sand and burn them.
They get covered in glass.

Goro's Lair - Uppercut victim into spiked ceiling
Bell Tower - Uppercut victim so they fall through a few floors and land on spikes, or uppercut victim into a bell, which loosens it and slams down on them, pushing them through the different floors until they die from being crushed or slammed on the spikes
Rooftop - Uppercut victims off the roof, and they slam on the ground like the Pit 2 fatality

I really wish that there were more Stage Fatalities... I was really hoping when NRS said that "most" of the stages would have fatalities, that it would be more than half. Sadly, only about 1/5 of the stages do.

Stage Fatalities I'd like to see implemented on existing stages:

Rooftop - I'd love to see the helicopter fly over and mow someone down with the mini-gun. Or the Dragon eat someone or catch them aflame. Or, of course, uppercut them off the roof down to the street, as mentioned a few times.

Armory - Have one of the guys in the background (the ones forging blades and such) pull and red-hot blade out of the forge, walk over to the loser of the match, and let the blade rest on their head, causing the blade to slowly melt through their body vertically, slicing them in half.

Goro's Lair - I'd love to see the spiked roof fatality here (as RockChalk mentioned). Or have Goro get up from his throne and pull off one of his fatalities at random.

Kahn's Coliseum - It'd be cool if a Destroyer in the background (whatever they are called, the big monsters) rip the loser limb from limb. Or have Shao Khan get up from his throne and pull off one of his fatalities at random.

Bell Tower - Throw the opponent into the gears, causing them to become mangled within the cogs.

rooftop - uppercut them off the building and they land on a car.

kahn's colliseum - shao kahn throws an energy spear at the loser's chest, killing them.

kahn's throne room - kahn's pet jumps on the loser and kills them.

evil tower - a shadow preist shoots energy at the loser, vaporizing them.

graveyard - you throw the loser into an empty grve, some zombie hands then grab them and pull them under ground.

Rooftop- The opponent is kicked off the side and barely hanging on with their finger tips. Then the winner walks over and kicks them in the face and sends them into the streets below, before being impaled on a street light.

Graveyard- The opponent in tossed violently into an open grave, causing the massive headstone to start leaning forward and falling into the hole which crushes the opponent.

Rooftop- Winner pushes loser to the side where they get to pick which stage fatality they want to do like Kratos Stage:
1. Helicopter shoots victim to death/uppercut into blades.
2. Dragon roasts victim alive/eats.
3.uppercuts off onto street

Colosseum- Shao Kahn releases one of the chained up people and they do their fatality(Tanya does neck snap).

Hell- scorpion comes out and does klassic fatality

Goro's Lair- MK2 Jade comes out and does Half-Mast Fatality

Shang Tsung'sGardens - Don't let the calmness of this arena fool you. Beneath the surface of the lake lies a sea serpent!

Input the fatality code and out of the lake a large sea serpent emerges! You hurl the opponent into the air and the creature lunges and snaps the loser in half in a single bite!

It then submerges into the lake. FATALITY!

That's a good one!