I got an InCase that's a combo of cotton and leather. At first I didn't like it because it felt like the iPhone was going to fall out, but maybe it's because the iPhone stretched it out, but it feels more secure.
i got the Speck one they're selling at the apple store that comes with two rubberized cases and a belt clip in the pack. On this one theres a flap that covers the bottom portion where the phone button is that got stretched out when i put it on and never snapped back which kinda sucked. I cut that flap off and now its fine. All you really need is a case that protects the edges and adds some grip IMHO.
i cant comment on the belt clip as i dont use it, thats a level of dorkdom i'm not willing to embrace.