I guess it would have been a success at first, but would be even more niche (or forgotten) now. The original Starfox is a fun game but still feels like a museum exhibit rather than an actual game these days. Doom just hit all the sweet spots at the time, which is why it is still remembered as a classic today (and Doom 3 isn't.)
Imagine Doom released a couple of years earlier than it did, or even in the late 80s. The gameplay is exactly the same, fast and smooth. The controls are just as fluid. The sound is just as kickass. The levels are just as complex, with all their nooks, crannies and secrets.
But there is only one catch: there are no textures. Every wall and floor is a solid color polygon, perhaps shaded with the same distance-mapping lighting used by Doom. There might be a few "polygon textures" here and there, some composite polygon walls etc. but no true raster textures.
Would Doom still be a big hit, with everything we love about it -minus the graphics- still going for it?
IMO, yes: the gameplay would still blow anything else available at the time out of the water. In general, anything using polygon graphics at the time was boring/complex, usually simulation titles. True 3D action games were few and far between, and surely nothing like a "first person polygon-based FPS" existed (military/flight sims don't count, IMO).
Being polygon-based might even give it a few perks, like real freelook/freeaim, the possibility of having truly 3D levels or decoration (though that capability might be foregone for mapping simplicity, with the levels still being 2D but with finally rendered with a proper 3D perspective). It might also allow Doom to be released a few years earlier than it did, though not MUCh earlier: polygon-based 3D games could grow quite demanding too (getting a smooth framerate from a game like e.g. 4D Sports Racing or Microprose Grand Prix required a 486 at full detail, and those were 1990/1992 titles!).
Sprites and monsters might still be 2D, or they could be polygon based 3D models too...in that latter case there's an obvious risk of making everything look much more ridiculous and "cyberspace-y". Voxels is another possiblity, but given the amount of work required to make animated voxels, I doubt id would've bothered.
So, what do you think? Would Doom still be a big innovator/a major gameplay singularity?