I tried to get by with a $10 original iPhone silicone cover, but that blocked the 3G's proximity sensor (which is bad because the screen won't disable when you put the iPhone to your face as you take a call).
The cover I really wanted was the Agent 18 ClearShield, which is very nice. I still have it and use it on occasion. I also bought a Marware CEO Premiere leather holster, which fit the iPhone well even with a cover on. While the ClearShield was nice, it is very FLASHY. If I'm not at a fancy party, flashy doesn't suit me very well. Also, the ClearShield is very slippery.
Then, I got a great deal on a black Griffin Wave case. This is one of my favorite cases and I used it for a very long time. I love how it's sleek, but not slippery. It has a matted feel but easily slips out of your pocket. The case is also somewhat transluscent so you can tell I have a white iPhone without blinding you with that fact. The one downfall about this case is that it has a two-piece design. The one time I dropped the phone about 5 feet onto concrete, the cover came off on impact and slightly scuffed the bezel. Although there was no major damage, it was a shame that I couldn't get FULL protection with that design.So, finally, I came across the Contour Showcase for the iPhone 3G (shown in picture). The case itself is a one-piece design and it comes with a holster. I have accidentally dropped the phone with and without the holster and it holds up very, very well. No damage whatsoever. I love the holster because it has a vertical clip, which is exactly what I wanted. The clip also acts as a horizontal stand to watch movies.