Commander Keen in Invasion of the Vorticons - First smooth side-scroller I ever played
Doom - Smooth gory goodness that is
Few people realise that the overly cute, pogo-stick toting Commander Keen was also developed by John Carmack. I just love the fact that one mind could produce Keen, Doom, and Quake

Although, his interest has always been with the engine, not the actual game content, and you could see how he would've been happy to work on (as you said) an early smooth scrolling side-scroller.
True, but compare it to the other FPS titles available before Doom. Two shining examples were Wolfenstein 3D and Blake Stone: Aliens of Gold. Then Doom happened and it changed everything forever.
Agreed. Doom took massive strides in terms of feel, smoothness, using the engine to help with storytelling (think lighting used for jump scares), sound design and very intelligent map design.
Compared to NFS III
Another Game changer of a title would be half life, it was immersive and realistic as F7*CK when it came out on 1998, it was literally the first intelligent shooter.
So many fond memories of Hot Pursuit mode! Either the direct follow up to NFS 3, or the next one after also introduced decent damage models, which was quite impressive for it's time, even if it wasn't implemented in a way that was very fun. One of the NFS's of that era also introduced Pink Slip racing, which I haven't really seen since..
I also consider HL to be hugely revolutionary, mostly for the fact that they managed to produce a story rich FPS with a silent protagonist. The scripted events, AI, and superlative mapping tools made for a massively fulfilling single player experience, and opened up the game for a plethora of amazing mods. It's still the best game made to date, IMO.
My submission to this thread is similar to [MENTION=1349]Tsar[/MENTION]'s: Morrowind. The first truly sandbox game I played, and with a rich world with interesting distractions. I should load it up again.