Crow: Your system seems to meet the requirements. You can purchase a suitable video card for under $100 (or as low as $50). As frubsen said, ATI Radeons are nice, so are the Geforce 2s.
Also, there is a patch for GTA III, available somewhere, probably rockstar games. This will upgrade to version 1.1. Make sure you try running your game at the lowest resolution also.