DooM: Early builds had interesting things like a rifle with bayonet (hence why Doomguy's sprite and the zombiemen both carry rifles), collectibles like Wolfenstein 3D's treasure, and mockup UIs that include things like an inventory and a radio log. The Doom Bible also includes tons of interesting ideas that were left on the chopping block, including a story that was actually significant, multiple player characters (recycled for Rise of the Triad), and a completely different setting. (Tei Tenga, the only remnant of this is one of the computer screen wall textures) It seems that much like Wolf3D before it, Doom was much more ambitious, then scaled back to make it more accessible.
Jazz Jackrabbit 2: JJ2 had a lot of cut content including powerups, levels, even entire bosses, one of which is fully coded and just requires sprites for its hitboxes to work. The laser shield, for one, was really interesting but incomplete and only destroys block if you throw it in via the level editor.
Banjo-Tooie: Bottles' Revenge, an extra mode where player 2 could control Bottles' ghost and possess enemies to attack Banjo with. It's dummied out, but still mostly functional with some Gameshark tomfoolery or ROM editing. For that matter, Stop 'n' Swop[sic]. I understand the reasons why they were required to scrap the plans, but I can't help but miss the idea of what could have been.
Starfox Adventures: Basically the entire game before it became Starfox Adventures. I actually love the game despite its numerous flaws, but it only suffered from shoehorning in the Starfox license. Had they left it as Dinosaur Planet, with a totally original story, I feel it may have been more pleasantly remembered.
Daggerfall: A great deal. Whole factions, enemy types, abilities, spell triggers, and more didn't make the cut. Granted the game was a barely functional mess as it was (heck, the main story was bugged and uncompletable in version 1.0!), but I can't help but wonder what it would have been like to join a faction called The Order of the Lamp.
Quake: The original idea teased in Commander Keen, specifically. Instead of being a mostly nonsensical shooter, it was to be an open-world RPG, and Quake was the name of the player character. It seemed poised to strike against the idea of the roguelike start making you "a weakling with no food" and having you begin as the strongest man in the world. I believe the original working title was The Fight For Justice.