Here's my PC situation:
Athlon XP 2200+ (around 1.8 ghz)
512 MB RAM
WinXP SP1
Onboard graphics, 64 MB Geforce 4 MX
It's a cripplingly slow machine by today's standards, but it still runs Icewind Dale and Quest For Glory just fine, and all my emulators, though some games on DosBOX run too slowly to play.
If I'm looking to play Redneck Rampage, Fallout, Operation Flashpoint, etc., am I going to have to upgrade? If so, how far up should I go? Keep in mind that I have an unused AGP slot, and a few PCI. No PCI Express for me.

I'm pretty sure you'll be able to play all the games you listed. I used to play flashpoint when it first came out on an old 750mhz Athlon (albeit with most of the settings on minimum, but it was still playable), so it should run pretty comfortably on your rig.

Man.. It's been a long time since I tried HW like that, but if memory serves, 3D games later than DX5 won't run well on it. They'll work, but they won't be much fun to play.
Fallout & 2D games in general shouldn't be a problem though.The GF4MX is pretty horrible. Maybe 2/3rds as fast as my old 32MB Oxygen. Really, it was an insultingly poor bit of hardware.

I don't know if you can upgrade your RAm, if you can go to 1 GB it should run you less than $20.
Video cards... I could run up to Neverwinter Nights 1 on an NVidia GeForce 5200, you can pick an AGP version up for about $35 from TigerDirect, a 6200 will set you back $40. They sort of stick those of us who still have AGP slots, the "trickle-down" effect (cost-to-vid card-quality ratio) isn't as good or quick as for PCIExpress cards.

These games should run just fine.

... And you really should install the Service Packs :P

Those things scare me. I had so many friends go to SP2 and it hosed their install, they had to start from scratch.

Ahah, that was like 3 years ago. Everything is now stable heh.. It takes time with Microsoft ;>

Fallout will definitely be fine. Redneck Rampage might run slow due to DOSBox, I've seen it chug on more powerful machines.

There are ways to alleviate that, check out the Redneck rampage thread. I've had issues, but I've been able to overthrow them easily by changing the rendering modes, resolution, and sound.

You're joking, right? You can't seriously mean that his machine can only run games built on versions of DirectX which preceded 3D hardware acceleration, especially since the GF4MX, poor though it was, was released in the same year as DX9.0.
In my experience with a relatively comparable machine - a laptop with a P4 2.4GHz, 512MB RAM, and a 32MB GF4 Go - you should be able to play most of the games on GoG acceptably. Unfortunately, acceptably doesn't include pixel shaders (which the GF4MX line lacks), but should also preclude rendering lag with appropriate rendering settings selected.
Actually, you should have been able to run NWN1 just as well on a GF2, according to the specs. Of course, it's probably worth the investment should snarfbucket want to run anything even remotely involving shaders. The same goes for the RAM - it won't do much for most games coming off of GoG, but it might be worthwhile in order to run something on at least the level of Sacred.

The bottleneck has got to be the onboard graphics and SP1 of XP. Do upgrade to SP2 at the very least, SP3 even more so recommended.
As for upgrade options, maybe you can get a 2nd hand AGP gfx card and a ram boost to 1 or 2GB. Of course, a better option would be to get a completely new PC, if you got spare cash.