I'll preempt this by saying: measure your case/components first to make sure parts will fit.
I read on the HP forums that someone fit a 3.4"x5.9"x5.5" power supply into the P7-1003.
The PSUs below are 3.4"x5.9"x6.3", make sure you have the extra space.
The video cards are going to be 10"-11.5" depending, measure from the back of the case to whatever you run in to, probably the metal cage in the front.
$95 : Corsair TX650 V2
$90 : OCZ ModXStream Pro 700w
$500 : EVGA Superclocked GTX 580
$350 : EVGA Superclocked GTX 570
$350 : XFX HD 6970
$290 : Sapphire HD 6950
This is to give you an idea of price, these are the more top-end choices.
Either of the PSUs will power any of the cards.
I looked specifically at cards that would vent out of the case since I don't think air-flow is too good inside.
*Edit - Guide to replacing your PSU:
Please read through the thread thoroughly before responding.
Nobody wants to read a wall of text, formatting is your friend.
i5 3570k | 8GB G.Skill 1600MHz | R9 290 | SeaSonic 750X