According to the specs of the P4C800-E deluxe motherboard it has one AGP and 5 PCI slots. You can only place a PCI (not PCI-E) or an AGP card into your computer, AGP is better/faster than PCI cards.
The best graphics card you can place into your computer is the HD3850 AGP card. It will mostlikely be bottlenecked by your CPU, so overclocking will give you more performance.http://www.newegg.com/Product/Product.aspx?Item=N82E16814102730&cm_re=agp_3850-_-14-102-730-_-Product
You mostlikely will need to upgrade your PSU to 450watts in order to use this card.
Also if you are looking to upgrade both the PSU and graphics card you might as well look into upgrading the whole system to a new one, as it will give you better performance for the amount you will spend.