Half-Life 1 could also do colored lighting in software, the software-rendered and accelerated versions looked almost identical aside from the texture filtering.
Big difference from what I remember was water rendering with the software mode having some fun effects.
True perspective-correct 3D texturing (as opposed to the fake 3D in the DOOM engine, or the affine texturing of the PSX) on a 90 Mhz Pentium CPU.
Sure, the resolution was low (I think we were still in 320x200?), but that still doesn't give a lot of clock cycles for each pixel. 320x200 at 30 fps is 1,920,000 pixels per second. At 90 Mhz, that's only about 45 clock cycles per pixel on an architecture that could take several clock cycles per instruction.
The software renderer didn't do colored lights, but it still did dynamic lights from rockets and grenades, IIRC.
EDIT: Just realized we were talking about Quake II, not the first Quake. Whatever, still impressive.
The surface-building inner loop is particular efficient, because it consists of nothing more than interpolating intensity, combining it with a texel and using the result to look up a lit texel color, and storing the results with a dword write every four texels. In assembly language, we've gotten this code down to 2.25 cycles per lit texel in Quake. Similarly, the texture-mapping inner loop, which overlaps an FDIV for floating-point perspective correction with integer pixel drawing in 16-pixel bursts, has been squeezed down to 7.5 cycles per pixel on a Pentium, so the combined inner loop times for building and drawing a surface is roughly in the neighborhood of 10 cycles per pixel.
In OpenGL mode colored lighting is there. But map designers overused it too much, especially in outdoor locations having yellow sky lighting, which looks somewhat depressive.