You should get something that costs as much as what you paid originally for GTX580...
When my 8800 died, I got GTX280, which was a hell of a bump (in your terms think suddenly getting GTX780 for free).
Ofc maybe I was just lucky or MSI felt generous, but that's what happened for me. (Although it died in one year and then no warranty anymore
)