Upgrading my HP Pavilion 750n

Ok, this would be part 2 of my upgrades on my computer, after I Upgrade my pentium 4 1.6ghz processor, I want to get a new graphics card, I was hoping for something that was 256mb or more somthing that would do a good job for gaming an all that good stuff. My computer is an HP pavilion 750n and at the moment I have a NVidia TNT2 M64, in otherwords the worst graphics card ever made. It wont play anything I want it too. I can barely play old games let alone anything that has come out in the past 7 years. My problem is I don't know what I can buy in terms of compatibility. I know the basics about computers but I don't want to buy anything that won't work in my computer. I know that I need a agp 4x compatible graphics card, but I don't know if theres any other specifications I need to be aware of when purchasing a graphics card. Will any card that is AGP 4x compatible work for my PC? I am currently looking at CPU's so I can upgrade the one I have. (I have another post about upgrading my CPU in the CPU forum) But it has come to my attention that my CPU will also be a determining factor in what kind of graphics card I get, why is that? What will I need to make sure is the same between my CPU and my graphics card? Also, what would be a good graphics card for my computer. I also heard that ram is a big factor in what type of graphics card to buy.