Duke Nukem 3D was released in 1996, which is firmly in the PCI-based Socket 7 era. Intel’s Pentium was available at speeds up to 166MHz (200MHz later in 1996), and a variety of x86 CPUs from other manufacturers were available too.
A 133MHz Pentium (or similar; I had a 133MHz Cyrix 6x86 166+) paired with a not-rubbish PCI graphics card can run Duke Nukem 3D reasonably smoothly at 640×480 — at least, compared to expectations at the time, when no one expected anything like 60fps from a FPS on PCs; this Phil’s Computer Lab video shows between 31 and 51fps, depending on the graphics card, on a 233MHz Intel Pentium MMX. 800×600 would be a stretch though, probably until 400-500MHz CPUs.
The limiting factors for Duke Nukem 3D are integer performance and the speed at which data can be transferred to VRAM. So higher MHz and faster RAM and VRAM would all help.