I have two classics (80GB and 120GB) and I got a black leather case for each of them. When I got my first classic three years ago, I bought a silicon case, which was fine, but not as nice - or as comfortable - as the leather. However, leather tends not to be the cheapest option, which, given the price you have paid for your iPod, may be a consideration.
One of the cases is a Gear4 - I got it in the same store I bought my MBP - and it is a nice leather case. The other one is a DIO, which I bought in an airport shop, and it is a softer case.
Cheers and good luck