Here are all the stage fatalities I remember.
In Mortal Kombat 1, on The Pit (the bridge) you can uppercut someone after defeating them and they fall onto the spikes below. On the Super Nintendo version this was sanitised and all the blood and bodies had been cleaned up. I think they are diffirent in Mortal Kombat Trilogy.
In Mortal Kombat 2, there are three fatalities you can perform. On the Deal Pool, you can knock your opponant into the acid after defeating them by holding low punch and low kick when doing an uppercut. You see them fall in and their skeleton will be seen floating a moment later. Keep holding the buttons and soneone will go "oh". On the Tomb stage, you can uppercut your opponant into the spikes. Each character has a combination to do this. On The Pit II the same combination will knock them off. I think they just fall to the bottom.
In Mortal Kombat 3, there are three stages where a specific combination will perform a fatality. On the Subway, your opponant is knocked onto another railway, where a train runs them down. On Khan's Tower, your opponant is sent through the floor and they fall down, breaking through the floorboards, until they are impaled on spikes, On The Pit 3, your opponant is knocked off and blades made out of bone tear them apart.
I think there is a cheat in Ultimate Mortal Kombat where you knock your opponant into the green glowing thing in the Soul Chamber, which unlocks secret characters including one named Pedro.
In Mortal Kombat 4, there's a stage with a fan that you can knock your opponant into, slicing them up. Also, the continue screen has your character falling. Don't continue and they are imapled on spikes, ala The Pit.