I've generally noticed that wider tires make a big difference. For instance, I bought a road bike with 23mm wide tires and it was just unusable, it would get flats every other ride.

Over the past 5-10 years there's been a trend towards wider rims, thankfully. Before that, a lot of road bike frames couldn't even FIT a wheel over 25mm wide!