Although I've never owned one, I've been quite impressed by the appearance of the range of cases by Vaja. If I were to get an iPhone (which I probably won't at the current cost of ownership) or a new iPod, these would probably be my first choice:
http://www.vajacases.com