Yeah, I actually had a Voodoo Banshee in the late 90s. With a P3 450 mhz and 128 MB of RAM Q3 ran fairly well.
After running that way for a year or so, I eventually got a Voodoo5 5500, that was killer at Q3
Then after that a QF3, at which point frame rate simply wasn't an issue anymore.