I’ve been able to raise my FPS from a rock-solid… 15fps on Railgun, looking from the Axis spawn down past the Rail Gun, up to a solid 45-50 on my Kyro2 video card, running at any resolution from 640x480 to 1280x960 save during a firefight, and I’m running on a dual-1.4Ghz machine, though I know SMP doesn’t help that much with anything RTCW-based. 
Anyways, try console settings, switching variables around and what-not. What did it for me, as stupid as this will sound to most of you, was this:
seta r_primitives “0”
seta cg_atmosphericEffects “0”
Yes, that’s it. I just canned multitexturing and primitives.
r_primitives raised my FPS to a solid 30-35, while cg_atmosphericEffects bumped it another good 30-40% on the Kyro2, so now unless I have a smoke grenade land on top of my head, it runs like a dream. Whereas before, I was lucky to get a slideshow. And yes, that last variable turns off the rain, so you do lose some of the nice atmosphere, but it seriously bumps FPS on lower-end video cards.
Amusingly, whatever math is used for the fogging, by itself, is a serious FPS-hog on my machine also. Turning it off when testing with a devmap (I.E. Cheats enabled) raised my FPS up to a dead-pegged refresh-rate-locked 85fps at 800x600. I’m still wondering why that is exactly, but I’m not complaining that harshy. I’ve got it running at least now. 
I DO find it odd however, that the Radeon 9500 cards are having more of a problem running this game than GF3 cards, which by all rights they should be taking to the cleaners. As stupid as it sounds, anyone try renaming their executable to quake3.exe and see if suddenly their FPS goes up? =^.^=