The problem is the S3 card... that sounds pretty ancient, and S3 never made good video chips even back when they were in the biz. And they always seemed to have bad drivers, too.
I have an Nvidia Geforce 4 4600 and get about 50fps (because VSYNC is on). Yes, you need a video card that supports OpenGL, and all modern cards do. But that pretty much limits you to 2 companies, ATI and Nvidia. Any recent card by either company will be fine - a GeForce3, GeForce 4, GeForce 5 (aka GeForce FX), or ATI Radeon 7500 or above. For Nvidia cards, avoid the ones with "MX" in the name.
I would suggest going to
http://www.pricewatch.com/ to get a feel for prices, and if you're in the US, going to
www.newegg.com to actually buy a card, as newegg is reputable and cheap.
Specific recommendations, in order of what I'd probably buy:
Radeon 9800
Radeon 9700
Radeon 8500
Radeon 9600
Radeon 9500
Geforce FX 5900
Geforce FX 5600
Geforce4 TI 4600
Geforce4 TI 4400
Geforce4 TI 4200
Radeon 9200/9100/9000 (I don't know much about these)
GeForce4 MX 440
Some of these are pretty cheap. There's no sense in blowing over $100 on a video card unless you're going to buy Half Life 2, for example, or play other 3D games (which you probably do not, judging from your card).
-Cherry
P.S. The latest Matrox cards should be fine as well.
P.P.S. "All-in-Wonder" cards support TV's and multiple monitors and stuff. All three companies have cards with gizmos and multimonitor support in their drivers, but I can't advise you in that area. You may also want to try updating the drivers for your current card, though I suspect that's a lost cause.
[ November 22, 2003, 23:26: Message edited by: Saber Cherry ]