Lajo
That site is fucked up, keep Firefox away from it, but those are really good cases. I've got one for my 4th gen and I love it.
You can get them with wheel covers, screen covers, three different clip options, and even dock compatible if you want. When it comes to the soft skins, Lajo's are the best.
My 4th Gen is currently riding in a Matias iPod Armor case, which is also awesome, but not cheap. It fits all iPods, which means it makes my 4th Gen thicker than my 2nd, but when protection is paramount, it's the case.
Check out
Trendy Geek for cheap screen and metal covers that are almost invisible and can be used with other cases. They offer my iPod an extra, base level of scratch protection even when it's not in a case.