Throw It In: Gray Fox's presence as the Cyborg Ninja, not to mention the entire concept of the Cyborg Ninja, was not originally supposed to be in the game: Yoji Shinkawa suggested that they add in the concept because it seemed cool.
What Could Have Been: Hal Emmerich/Otacon's appearance was supposed to be more indicative of a combination of Dennis Nedry and Michael Moore (IE, an overweight slob with a baseball cap and always eating a chocolate bar). The design used in the final version was pitched in by Yoji Shinkawa as a way to rebel against it.
Decoy Octopus was supposed to have a boss fight, but it was scrapped due to them not being able to do what they wanted with it. Aspects of the fight were used in Metal Gear Solid 4 in the Laughing Octopus fight.