Ok, so basically my crap 733Mhz PC with an ATI RAGE 128 PRO card goes as fast as your computer- for some reason. Does your computer have dual cores? If so, (and as far as I know), Tremulous just lags with a PC containing dual cores unless you put in a console command to fix it.
Also, lowering the quality of the game is basically useless, as it only rose 10 frames for me, because Tremulous is dependent on the CPU. Also, maybe the servers you go to has high ping or too many structures on the screen (Ex. Unlimited Bp).