Faits: A. Par contrat du 8 septembre 1998, A._ Sàrl (ci-après: la locataire) a loué à X._, Y._ et Z._ (ci-après: les bailleurs) un local de 750 m2 pour l'exploitation d'un club de fitness; le bail, qui avait pris effet au 1er septembre 1998, portait sur une durée initiale de dix ans, puis était reconductible tacitement de cinq ans en cinq ans; le loyer mensuel convenu était de 5'650 fr., charges par 150 fr. comprises. Ce contrat annulait et remplaçait un précédent conclu le 7 novembre 1995 pour un loyer mensuel de 7'337 fr. 50, charges par 150 fr. comprises; lors de la signature du second contrat, les bailleurs ont consenti à une réduction du loyer en raison des difficultés financières rencontrées par la locataire. Les 30 août et 22 octobre 1999, la locataire a informé les bailleurs de l'infiltration d'eau dans la cafétéria et de dégâts matériels en résultant, respectivement d'une odeur nauséabonde qui se dégageait du vestiaire des dames; soulignant l'impact négatif provoqué dans un contexte fort concurrentiel sur la clientèle et sur de potentiels nouveaux adhérents lors de visites des locaux, elle les a enjoints à "faire immédiatement le nécessaire afin de remédier à ce désagrément"; un certain nombre d'échanges d'écrits et de démarches en rapport avec les défauts invoqués s'en sont suivis; le problème relatif aux odeurs a été réglé le 31 juillet 2005. Le 3 octobre 2005, la locataire a résilié le contrat de bail pour le 28 février 2006; elle s'est prévalue de l'art. 259b let. a CO, se plaignant du fait que les locaux ne permettaient pas l'exploitation commerciale d'un fitness. Les locaux litigieux ont été reloués le 1er avril 2007. B. Par demande du 29 décembre 2003, la locataire avait ouvert action contre les bailleurs; en dernier lieu, elle a réclamé à ses adverses parties le paiement de 266'000 fr. avec intérêts à 5 % dès le 1er octobre 2001 à titre de dommages-intérêts (art. 259e CO) et, subsidiairement, requis une réduction de loyer de 55 % durant toute la durée du bail (art. 259d CO). Le 27 mai 2009, le Juge III du district de Sion a condamné les bailleurs à verser, solidairement entre eux, à la locataire 158'515 fr. 60 avec intérêts à 5 % dès le 1er décembre 2002. Par jugement du 19 mai 2010, la Cour civile I du Tribunal cantonal valaisan a partiellement admis l'appel des bailleurs et réduit le montant alloué à la locataire à 101'509 fr.; en bref, elle a admis l'existence de défauts - dont la gravité était de moyenne importance - imputables aux seuls bailleurs, à l'exclusion de la locataire; elle n'a pas alloué à la locataire de dommages-intérêts, dans la mesure où elle n'avait pas pu acquérir la certitude que le montant du dommage éprouvé par celle-ci correspondait à la perte telle que chiffrée par les experts; elle lui a en revanche accordé une réduction du loyer au taux de 10 % du 30 août au 22 octobre 1999 à raison des problèmes d'étanchéité, de 35 % du 23 octobre 1999 au 31 juillet 2005 pour tenir compte du fait que la locataire avait également été confrontée à des problèmes de mauvaises odeurs et de 20 % jusqu'au départ de la locataire le 28 février 2006, période durant laquelle seul le premier défaut avait subsisté, d'où un total de 140'811 fr.; elle a enfin considéré que le congé donné par la locataire était nul pour cause de non-respect des conditions de l'art. 259b let. a CO, de sorte que les bailleurs pouvaient prétendre à des dommages-intérêts sur la base de l'art. 264 CO relatif à la restitution anticipée de la chose; à ce titre, elle leur a alloué 10'000 fr. correspondant à un solde impayé pour l'achat des installations fixes, 24'600 fr. de perte locative et 4'702 fr. 60 (arrondi à 4'702 fr.) pour la mise hors service des bains turcs/ hammams; elle a en revanche écarté notamment une prétention de 15'011 fr. 35 pour la remise en état des locaux; en définitive, les bailleurs pouvaient donc invoquer 39'302 fr. en compensation. C. Les bailleurs (les recourants) forment un recours en matière civile au Tribunal fédéral, concluant à l'annulation du jugement du 19 mai 2010 et au rejet de la demande, subsidiairement au renvoi du dossier à la cour cantonale pour nouvelle décision dans le sens des considérants. La locataire (l'intimée) propose le rejet du recours.