Dug up something relevant from my old internet archive: Tom Pabst's "Quake Video Benchmark Survey" (sysdoc.pair.com), a crowdsourced database started 10/27/96, 1490 entries collected up to 7/1/97, all run at 640x480. Attaching the raw HTML (quakeresult.7z) - I actually submitted a result to this survey back in the day, so I can vouch for the resolution firsthand.
My own entry: Pentium 100 (P54C, no MMX) + Tseng Labs ET4000 W32P (2MB DRAM, PCI, Univbe 5.3) = 10 fps at 640x480.
Filtering the file for P166/P200 entries with Matrox Millennium/Mystique (genuine software rendering - the Virge/Verite entries in the same file are flagged "Special 3D enhanced Quake version" and use a different, accelerated render path, so those don't count for this comparison):
- P166 (P54C) + Matrox Mystique: 32.2 fps
- P166 (P54C) + Matrox Millennium: 29.8 fps
- P200 Pro + Matrox Millennium: 27.1 fps
- P166 (P54C) + Matrox Millennium: 23.1 fps
- P200 MMX + Matrox Millennium: 25.0 fps
- P200 Pro + Matrox Mystique: 21.8 fps
So the honest answer to the original question: it depended heavily on the video card, not just the CPU. My own P100 with a mediocre Tseng ET4000 only managed 10fps at 640x480 - well below playable. But a P166/200 paired with a fast WRAM/SGRAM card like the Matrox Millennium or Mystique could clear 25-32fps at the same resolution, genuinely smooth by 1996 standards. Cheap SVGA/VLB cards with slow bank-switching were the real bottleneck for a lot of people, not the CPU.