Here's the system:

ASRock P45 (The one with DDR2/DDR3) (I have a MSI P6N 650i-based bored, too)
C2Duo E6400 (overclocked from stock to 3.0GHz depending on the mood)
Cooled by OCZ Vendetta2 120m HDT
2x 2GB DDR2-800 Corsair "Gaming" Memory from Best Buy (I used to work there and got a sick deal)
GeForce 9600GT 512MB (Again, sick deal from working there at BBY)

I plan on upgrading to i7 in the future when they have better selection/not X58, but will have an interim step of E8500 before. I don't want to overclock (I've fried 2 mem chips, a motherboard, and a PSU out doing that now from stress and an oops-moment where I went a little crazy with voltages.)

Now, here is where I'm stuck: Which will be most beneficial to my upgrade cycle NOW?
I know, no matter which piece I update, the others are going to bottleneck me.

If I get a GPU, my CPU can't feed it.
If I get a CPU, my GPU won't feed it, AND my memory will gimp the CPU
If I get memory, the impact will only be slight.

My Choices (for those tl;dr, which to get first?):

C2 Duo E8500 CPU
AMD 4870 1GB GPU
4 GB (3x 2GB with one sitting out) Memory.

WHAT TO DO!

Well, the reason I wanna change the ram is that there is a documented impact of running DDR3 mem on E8500 vs DDR2 if available. It's marginal, but it's there, and that would niggle at me and I can't handle that. On top, I'm planning on transitioning to i7 which uses DDR3, my mobo has transitional DDR3 slots, and E8500 likes DDR3. So, I'm trying to be a little forward with it.

Anyway, Can the E6400 still feed even a 4870? Last I remember, I swear the E6400 could barely feed a 8800GTS let alone an 4870...

I have a dual core cpu 3.0ghz not overclocked for the moment, with the 48701gb and it seems to do good enough, plus the problems with most of todays games are the graphics power required, not so much cpu, get the 4870 and you should be fine

Your CPU OCed to 3GHz should give you about the same results as a stock E8400 which is more than enough for most games and wouldn't bottleneck you. So my choice would be to go for the GPU first. After that, either jump to i7 or get a quad like the Q9550 if the price drop is interesting and games start really using those cores.

Some kind soul worked out a proc over a year in a recent thread, with 6 hours usage a day and it came out at $25 per annum so would not even factor in power consumption.

I'm voting for GPU upgrade 1st, CPU second, RAM very last.

Frankly, I see no reason why you need to upgrade your RAM at this point. Don't think you're going to realize any real-true value from it yet. Save your DDR3 money for when you DO get your i7. By then, DDR3 will hopefully come down a little bit in price anyhow.

GPU is your weakest link of the three.