Sim... anything. Even The Sims. While tycoon games have always had a healthy ecosystem, nobody has ever quite cracked Sim- games like Maxis.
A lot of people say Doom, but Wolfenstein 3D was the first FPS. Doom did give us stairs, while Quake actually gave you the first full FPS experience by freeing your view/aim to look up and down. The only other interesting technical evolutions for the FPS genre I can think of is SWAT 3 giving us environmental bullet penetration (sorry COD:MW fanboys) and Red Faction's destructible environments.
RTS is my real love, though, so I know them the best. Dune II is a big grand-daddy of modern RTS. Command & Conquer broke the RTS multiplayer mould, followed by Total Annihilation introducing RTS to both 3D environments and a different scale of engagement (huge numbers of units and massive playing fields). Age of Empires went in a different direction, fathering the slower, more Civilisation-like RTS games (without falling into the turn-based category). Starcraft managed to turn RTS games in a professional sport.
Homeworld is the daddy of 3D playing-field RTS. Machines was the first attempt at an RTS/FPS hybrid. Ground Control was another groundbreaker, fathering what is now considered the RTT (real time tactics) genre, although line remains blurry to this day (see a lot of Relic games- Dawn of War series, Company of Heroes). DarkSpace is the first and oldest MMORTS. Natural Selection was the first RTS that fully merged the RTS and FPS genres where every 'unit' was capable of being a human player. Savage: The Battle for Newerth went one further, integrating RPG elements into the RTS/FPS hybrid. Dawn of War gave us control-point based resources. Company of Heroes was the first RTS to use Havok physics in order to have highly destructible environments (Age of Empires 3 had Havok first, but only for dynamic destruction animations). Achron is the first RTS to fully embrace time-travel as a core game mechanic.
Of all those games, pre-Starcraft in that list may be increasingly difficult to locate copies of, run and enjoy (due to a lack of many conveniences modern RTS'ers might take for granted). Also both Natural Selection and Savage may have dwindling communities comprised of mostly hardcore players and, as pure multiplayer orientated games, be challenging to get into.
