The Speck ToughSkin is the best protection I have seen and used for iPhones, and some iPod Touches as well. Problem is, Speck hasn't updated their product line for either the new iPhone 4 or the 3G and 4G Touch.
Keep checking their site for updates - or email them and ask them - WHEN???, as I already have, but I think more voices would be helpful.
The ToughSkin has a holster with a built-in stand, the case has an internal "skeleton" and is made of neoprene-like silicon, very thick, very substantial with extra thickness on the corners, and has the surest grip of any case I have used. It also has a shield for the screen and several extra shields, though I still have the original protector on a year and several months after I installed the first one. I work in extreme environments and this case has proven itself over and over, my phone has survived several five-to-six foot drops onto concrete.
The only improvement I would ask for is a little more dust/moisture protection around the dock connector/headphone jack and it would be perfect, but then there would be no room for improvement!
p.s. I don't work for Speck, and in fact, don't really like any of their other products, but this one is a winner in my books...
dmz