Some tires are tougher than others - Panaracer Pasela TG, Rivendell Ruffy Tuffies, Continenal Gatorskins. All these guys have some kind of belt that helps prevent flats (I call my Pasellas bomb proof, I've had 3 flats in 4 years). As opposed to what I call tissue paper tires - Michelin Race something or others. I have a friend who rides the Michelins - one day she had 7 flats! You might also check out cyclocross tires.

Can't help with the slime question, I've never used it.