Speed isn't so much of a factor, obviously, but the lower the rolling resistance the less sweaty I am when I get there. Then there's flats to consider. Basically the tire has to never get them because I can't be late. So what size would you ride?
For my commuting needs, I use Continental Gatorskins 700x28c. I also use Mr Tuffy liners to help protect against punctures. Using this combination, I haven't had a flat in 2 years. Before going to this combination, I would get about 1 flat a month. I travel about 14 km a day, 5 days a week, April to the end of November.
I recommend that you leave enough time in your commute to change a flat if need be. For me, this is only about 10 minutes. Your time may vary. My job is such that it's not a big deal if I'm a few minutes late. If your job requires you to be right on time, you may have to sacrifice being early on the off chance you do get a flat.
Also, ensure that your tires do have enough air in them. If you use skinny tires, a lot of flats come from snakebite flats, caused by not enough air pressure.
Personally I prefer the Schwalbe Marathon Plus tyres in a sensible width, 28 will do nicely or 1.5 (instead of 1.35) if using MTB or folding bike. To the pressure written on the sidewall, checked weekly for embedded glass and correct pressure.
The likelihood of getting flats on properly maintained Marathon Plus is practically zero. On every other tyre brand that I have tried this has not been the case, even if they come with a guarantee. With the Marathon Plus you can go out of your way to deliberately go through glass, for all other tyres glass is akin to Kryptonite.
The truth about the commute is that you learn every bump on the road but there is a lot of traffic and you have to be properly prepared to ride through the rough if you are to make good time.
On the commute it does take me 20 minutes to fix a flat. That is with correct tools and fresh tube. If I get two flats and have to stick on a patch (separate incident) it still takes 20 minutes. Notionally I can fix a tyre quicker than that but in practice this is not the case.
I don't leave 20 minutes earlier just in case I get a puncture, so long as it does not happen too often one can call ahead. Motorists in their cramped-yet-huge tin boxes are regularly a lot later than that.
Tire size is not a sure indicator of flat resistance. As Kibbee notes, proper inflation pressure, road character, riding style.... All factors.
I rarely get flats; can't remember when I had one last riding on the road.
However, they are as inevitable as anything else in life. A good, durable 28mm tire is nice compromise between super-skinny "racing" tires and something you might put on a hybrid.
Avoid tires with tiny little cuts or "sipes", these tend to trap road debris and it will gradually work it's way through the casing. Check pressures frequently, don't use super-light-weight tubes, etc. Watch the road! Potholes, new pavement seams, broken glass and such from auto accidents (or car theft!) are all hazards that can generally be avoided. And carry everything you need to fix a flat....Just in case.
I use a 23mm Continential GP4000S on the front. I love these tyres. They're super sticky and I've never had one slip out(!!)
On the back I'm trialling 23mm Continental Gatorskins. They are cheaper and since the rear wears out so much faster than the front I'm hoping they'll still grip well but not cost me too much. So far I've been riding on it for about 3 weeks and have had no trouble.
My bike (2010 Kona Dr Dew) came with 700x32 Continental Contact tires.
I've had the bike for 3.5 months so far: i.e. about 160 hours of commuting.
I've had 1 flat so far (front tire): caused by an impressively sharp, 3/4 inch nail through the tire. I don't know what tire could withstand that. When the bike tech replaced the tube for me (my first flat: I wanted to watch how he did it) I asked whether it had Slime in it and he said no: it's too heavy.
I don't always bother to avoid bumps and cracks and small pot-holes: apparently the wheels can take it.
The tires are OK on snow, too, going a bit cautiously; though not on ice.
They say 85 psi on the side. I try to inflate them to 95..100 psi each weekend, and they measure at 80 psi by the next weekend.
Well, obviously a lot depends on how far you travel and what the roads are like -- long distances over smooth suburban highways you want a bit narrower tire than for shorter distances or rougher, more urban streets. But generally there's no point in going narrower than about 28 -- the savings in rolling/wind resistance would only be of interest to a racer -- and likely there'd be little advantage in going below 35 or so, if the route is at all rough. Just be sure to keep your tire pressure up in the 80-100 range, near the top of the sidewall rating (something that also is important to prevent snakebite punctures).
What you definitely DO want is Kevlar-belted tires. The puncture resistance of Kevlar tires is 5-10 times greater than standard tires, especially in the narrower, lighter sizes. My current tires (35mm Kevlar-belted touring tires) have 3000-5000 miles on them and have never had a puncture.
The reason road bikes generally run narrow, high pressure tires is to benefit from lower rolling resistance. It allows higher speeds, with less effort.
I run Schwalbe Ultremo DD tires in 23c. They have excellent, sticky feeling traction, roll fast and smooth, and use a high Thread per Inch casing which helps with flats, as well as having a Kevlar anti flat layer built into the rubber surface. The DD stands for Double Defense.
It's always a fine balance between flat protection and ride quality. But tire width is not a major concern, assuming you're using tires appropriate to your bike and your riding style.
It's worth noting that tire weight will affect the amount of work you have to do. It's most noticeable when changing from worn to new tires, but I'm kind of regretting fitting 28s because my old 25s were lighter. You have to maintain the rotating inertia of your tires, so it's not just rolling resistance, but also tire and rim weight that will affect the effort you will have to expend to maintain speed. This higher inertia will also make your bike more stable and slower to turn in. Bigger tires basically allow you to be more comfortable. Taller sidewalls, more available flex, and you can run slightly lower pressure and still avoid flats. I'm a big guy and I don't think 28s are really necessary, but they will increase the rigor of your workout, which is why I'm leaving them on. If you want to breeze quickly through your commute, you'll be fine with smaller tires
Using 23mm tires on commuter for several years and feeling excellent, don't see any need to increase the size. Always commuting on asphalt only. Very seldom getting out on gravel and it is not that bad too.
Used Kenda, Panaracer, Michelin (Pro3 and Pro4) and Continental (4000). Michelin remain the distant favourite among all - the most sticky and comfortable tires.
During the last 5 years got only two flats. The first one was on Kenda tires - they were not good anyway, and the second on Panaracer, because tires were work out to the point of exposing large portions of wireframe.