I also vote the Otterbox Defender Case.
I'm a firefighter and have put my 4S through some tough environments. Unfortunately, the cases have taken a beating, but my phone has always been safe and still looks as good as it did day 1.
My selling point for the Otterbox cases is their warranty. Lifetime warranty with a purchase of their defender case (Unless they changed it). I've replaced 3 in just over a year (Damages I caused) and they shipped one out after confirming where/when I bought it. Was very easy process.