For a 20+ mile commute I'd definitely want the Marathon Supremes that Alan recommended. I've got a 700x35 set on my main commuter and I'm expecting delivery today of a set of 26x1.6 for my Long Haul Trucker. I've had very good success with this tire -- two flats in 3000+ miles and both of those were wood screws that went straight into the tire.

On the other hand, your conditions sound very bad. I might be tempted to bite the bullet and mount a set of Marathon Plus in those conditions.