On older systems you mentiond (A500, 600, 2000) it is rather painful any way you cut it. The bare minimum I'd recomend is a 060 and Voodoo 3(Via Prometheus). Also newer Quake ports like GLQuake are MUCH better than Clickbooms.
HERE is an old benchmark comparison I did a few years back.
Test system:
A3000 MK-II 060/66 64meg ram
Prometheus w/Voodoo3 3000(SGRAM)
All tests done in full screen(no size reduction), the GLQuake68K version is using the fastrender option.
screenmode | Clickboom fps | GLQuake fps
320x240------------10.8-------------23.0
400x300-------------7.8--------------21.1
512x384-------------------------------21.1
640x480-------------------------------19.9
800x600-------------------------------16.0
1024x768-----------------------------11.9
:-o
-edit-
Removed Quake II results, irrelevant. Oops;-)