Overall Problem

Well the difference between a 9400 GT and a Radeon 4350 HD isn't as large as you'd think...

For example:

9400 GT
Memory Size: 512MB
Memory Interace: 64-bit
Effective Memory Clock: 800Mhz
Core Clock: 550
Stream Processors: 16 (x5 = 80)

4350:
Memory Size: 512MB
Memory Interface: 64-BIT
Effective Memory Clock: 1000Mhz
Core Clock: 600Mhz
Stream Processor Units: 80 (/5 = 16)

So there are small differences, but the cards will behave similarly. You might think there's a large difference between Stream Processors if you look at their specs, but NVIDIA's definition of Stream Processors is about 5 times more powerful than ATI's. So if NVIDIA has 16 and ATI has 80, you can guess that they're about equal. 16 x 5 = 80. This is because NVIDIA counts Stream Processors and ATI counts SP Units. According to the best data 5 units equals a processor, but thats up in the air because they're different techs. All in all they're similarly specced cards. If you want a real performance boost you're going to need a card with a higher Memory Interface and more Stream Processors. Examples Below:

9800 GT: $100
Memory: 512-1GB
Memory Interface: 256-Bit
Effective Memory Clock: 1800
Stream Processors: 112 (x5 = 560)
Core Clock: 550
Shader Clock: 1375


GTX 260: $220
Memory: 896MB
Memory Interface: 448 Bit
Effective Memory Clock: 1998-2106
Core Clock: 576-650
Stream Processors: 216 (x5 = 1080)
Shader Clock: 1200-1500

5850: $300
Memory Size: 1GB
Memory Interface: 256-bit
Effective Memory Clock: 1000MHz (4.0Gbps)
Core Clock: 725
Stream Processor Units: 1440 (/5 = 288)

You can find similar cards on the ATI side and depending on the manufacturer you'll get minute differences between the stream processor count and various clocks of the card. The memory interface and stream processors are the big factors on NVIDIA cards atleast.

Regarding GTA 4:
When we look at recommend system requirements, thats what it would take to run the game at medium settings. The system requirements are what it takes the game to run period. So when looking at this you'll see that the requirements are cards just one tier below yours. In other words, you won't be able to play the game at super high resolutions, but you'll be able to play it at medium settings comfortably.

* Processor: Intel Core 2 Quad 2.4GHz or equivalent AMD Phenom X3 2.1GHz
* Memory/RAM: 2.5 GB for XP or Vista
* Video Card: 512MB NVIDIA 8600 or 512MB ATI 3870
* Hard Disk Space: 18GB free
* Operating System: Windows XP SP3 or Windows Vista SP1

Well there are ways, you could turn off some of the visual requirements of Windows, but thats not as large a boost as people think. You could also turn down the settings in game, that'll help your computer process it faster.

However, if you really want to speed it up, I recommend buying a new card. Get a GTX 260 or 5xxx series if you can afford it, if not, get a 9800 GT or one of the higher end 4xxx series cards. Someone else will be able to tell you what the best ATI cards are, personally I always go for NVIDIA and the budget card is the 9800 GT w/ 1GB of ram, if you can afford it, its the GTX 260, if you're semi-rich it's the GTX 295, if you're loaded go for one of the brand new 480s.

See this tutorial: Optimize Windows 7