Firstly it's not just the graphics card which will solve all your problems, often it's a higher CPU as well. For example the difference in frame rates between a 700MHz CPU and 1000MHz for me (using the same graphics card) was between 8-10.
Which processor and motherboard do you have? This is important because the latest generation of graphics cards require a special slot called an AGP (Advanced Graphics Port). Chances are you have one but do verify.