I think that's probably true for console players, but I had already played Doom and Quake (which came out a year prior) before playing Goldeneye on my cousins' N64, so I already had expectations for first-person shooters, and I remember being frustrated that it was comparatively lacking in some areas, notably the controls. I seem to recall that you had to unlock the ability to use different controller input layouts, which seemed bizarre even then. Being used to mouse + WASD for gameplay made using a controller an adjustment, but I did recognize how great the 4-player splitscreen deathmatch was.
It definitely added more story and purposeful level design than the basic versions of Doom and Quake, although some of the id-based games like Strife and Hexen had already expanded on that a bit.
In answer to the original topic, I think it's probably either Super Mario Bros or Wolfenstein 3D, both of which while not the first of their respective genres established the basic systems used by their successors as well as achieving widespread appeal. They're a bit like the iPhone in that regard - not the first, but the first ones that everyone wanted, and what everyone else imitated thereafter.