Well I upgraded from a GTX 480 to a GTX 680, and the improvement was amazing.
At 1920x1080 with the Ultra setting's and max AF/AA I was getting between 35fps to 45fps on the GTX 480 whilst using around 1.3gb of Vram temp's were around 89c.
Same setting's on the GTX 680 gives me between 65fps to 75fps using 1.5gb of Vram, temp's are around 78c and the card cannot be heard when wearing headphones.
I am going to get a 2nd card at some point for when I eventually go for Triple monitor's, and overclock them once they are cooled under water.
My current card will do +175 on the core and +300 on the ram without touching the power setting's, if I mess with the power setting's it will go further but whilst it is on air I don't want to push it to far.
Really it is down to whether you want/need the card's that come with 4gb of ram, but if I had a GTX 580 I wouldn't have upgraded and instead I would have just grabbed another GTX 680 as the GTX 580's in sli give better performance that a single GTX 680.