I remember the first time I played Heretic, Hexen, Wolfenstein 3-D, Duke Nukem 3D and Doom. I was about ten or eleven years old back then. The mere ability to walk around and explore the "3D" environments from the eyes-view perspective alone was incredibly amazing. It was literally nothing less of magical, if only for the reason of being novel.
Then came Quake and I hated the clunky polygon models, unable to appreciate how much more versatile a true 3D engine was compared to the 2.5D shooters, because I had no understanding of the difference back then. For a pretty long while I was fairy indifferent towards the FPS genre although I did not give up on the 2.5D classics and eventually discovered more of them including Rise of the Triad. All the while being a huge fan of StarCraft and StarEdit. Then I chanced upon the demo of Will Rock which if you don't know is a Serious Sam clone set in Ancient Grome, and immediately took a strong liking to it, for exactly the same reason: you could explore awesome (or at least nice-looking) environments, and in addition encounters with monsters encouraged fast running and strafing across those nicely designed areas.
I vividly remember how my brain was deceived by both Doom and Will Rock: in Doom I tended to unconsciously lean sideways when dodging the imps' projectiles and much later in Will Rock I had that feeling in the stomach every time my character would be set off flying by a catapult. Both effects wore off pretty quickly once the brain realised that it was being duped, but this highlights an important factor that playing a fast paced first-person action game may provide for a similar kind of fun as actually playing a fast-paced physical game like football, which may have a certain appeal to players as well. (While your brain does realise that you're not actually moving yourself when playing an FPS, it still has to solve problems related to processing and reacting to visuospatial information.)