I got Quake II running on my computer. I
think I used the instructions on the page I linked above.
The installation involved a Linux Quake engine called quake2-r0.14.1-io2.i386.rpm. There was a newer version available, 0.15. The author said on his page he hadn't bothered testing it, but it should work fine. It doesn't; use the 0.14.1 version.
OK, correction. I got Quake II for Linux here:
http://www.icculus.org/quake2/