I've had similar experience with stick-on pads coming off. I tried nail-on pads and had some break (the pad just broke off the nail head), so I guess those depend on the quality of the particular one you buy. The ones shown in bib's answer look like much better quality than what I tried, which was basically just a plastic disk molded onto a nail.
I finally settled on screw-on "Magic Sliders" because I liked other products of theirs I had tried (you can find them at most big retailers, like Home Depot, probably Amazon):

These work on any kind of floor surface. I've found them to not mark hardwood floors (reviews for some other brands of similar design claim the other brands mark hardwood, so they may be a different type of plastic). Mine have been in use for several years and the glide surface is still smooth (if the plastic were to abrade and get rough, the glides would be likely to scratch the floor). Jim Stewart's answer mentions the problem of abrasive debris getting trapped in carpet-style glides. That isn't generally an issue with plastic-tipped glides.
They come in different diameters. Get the largest diameter that fits the leg, which will provide the most surface area, so the least tendency to leave a mark.
They do require drilling a pilot hole, but a screw provides a lot more strength than a nail.
One other style should be an improvement over stick-ons and are inexpensive. They generally look like this:

This particular one is from Home Depot and got mixed reviews (claimed the plastic scratched hardwood floors). I've never tried this style and can't recommend a particular one. This style has an adhesive backing, plus some tiny spikes. You tap it on to embed the spikes. The spikes keep the pad from sliding on the leg, which is what destroys the adhesive on adhesive-only pads. If you can find one with good reviews, they're essentially as easy to install as adhesive-only pads.