Faits:
A. Le 11 février 2005, la Commission Mesures structurelles du Grand Conseil du canton du Valais a présenté une motion visant à modifier la loi fixant le statut des fonctionnaires et employés de l'Etat du Valais (loi sur le statut des fonctionnaires, LSF; RS/VS 172.2), afin que les chefs de service soient engagés non plus comme fonctionnaires, mais par contrat de droit privé. Il s'agissait d'instituer une certaine souplesse dans l'organisation de l'administration et d'éviter notamment que "des structures ne perdurent qu'en raison d'un chef nommé dans un contexte révolu".
Dans sa réponse à la motion, le Conseil d'Etat valaisan estima que les objectifs de souplesse pouvaient être atteints dans le cadre de la législation existante; les mesures de réorganisation ne concernaient pas que les chefs de service.
La motion ayant été acceptée par le Grand Conseil valaisan le 13 mai 2005, le Conseil d'Etat a présenté un projet de loi visant à l'abolition du statut de fonctionnaire pour les chefs de service et à l'instauration de rapports de travail de droit public; cela permettait d'atteindre les buts visés par la motion et ne nécessitait pas, au contraire d'un engagement de droit privé, de changements d'ordre constitutionnel.
B. Le 14 février 2008, le Grand Conseil du canton du Valais a adopté la modification de la LSF, portant sur la modification des articles 1 al. 2 et 2 al. 2 dont la nouvelle teneur est la suivante:
Art. 1 Champ d'application
2Les dispositions de l'article 5 (durée de la période administrative), de l'article 6 (nomination et temps d'essai) ainsi que des articles 33 à 35 (résiliation et renouvellements des rapports de service) ne sont pas applicables aux chefs de service (rapport de droit public). Sont applicables à cet égard les dispositions du code des obligations en la matière.
Art. 2 Définition de la qualité de fonctionnaire et d'employé
2Sont considérés comme employés, sous rapport de droit public, les chefs de service et la personne qui est nommée à titre d'essai. Ils ne disposent pas du statut de fonctionnaire.
C. Gilles de Riedmatten ainsi que dix-neuf consorts, tous chefs de service au sein de l'administration cantonale valaisanne, forment un recours en matière de droit public. Ils concluent à l'annulation de la modification législative du 14 février 2008.
Le Grand Conseil valaisan conclut au rejet du recours dans la mesure où il est recevable.

Considérant en droit:
1. Selon l'<ref-law>, le Tribunal fédéral connaît des recours en matière de droit public contre les actes normatifs cantonaux. Les recourants ont agi dans le délai prévu à l'<ref-law>. La modification législative ne peut faire l'objet d'aucun recours cantonal, de sorte que le recours est directement recevable (<ref-law>). En tant que chefs de service dans l'administration cantonale, les recourants sont directement touchés par la réglementation attaquée; ils ont qualité pour agir (<ref-law>).
2. Les recourants se plaignent d'une inégalité de traitement contraire à l'art. 8 Cst. La modification législative traiterait les chefs de service différemment des autres employés de l'Etat, sans aucune raison objective, alors que les autres cadres supérieurs (directeurs, délégués ou adjoints du chef de service) ne sont pas touchés. Seule une quarantaine de personnes étant visée, l'argument de la flexibilité tomberait à faux. Par ailleurs, les chefs de service auraient le même statut que les personnes nommées à titre d'essai ou les auxiliaires, alors que leur fonction, hiérarchiquement élevée puisqu'elle comprend la délégation des compétences de la part des chefs de départements, implique une certaine durée. Les autres réglementations, fédérale et cantonales, prévoyant l'engagement de droit public, s'appliqueraient à l'ensemble du personnel de l'administration.
2.1 Dans le cadre d'un contrôle abstrait des normes, le Tribunal fédéral examine librement la conformité d'un acte normatif au droit constitutionnel. Il s'impose cependant une certaine retenue eu égard notamment aux principes découlant du fédéralisme et de la proportionnalité. Dans ce contexte, ce qui est décisif, c'est que la norme mise en cause puisse, d'après les principes d'interprétation reconnus, se voir attribuer un sens compatible avec les droits fondamentaux invoqués. Le Tribunal fédéral n'annule dès lors une norme cantonale que lorsque celle-ci ne se prête à aucune interprétation conforme à la Constitution fédérale ou à la Convention européenne des droits de l'homme. Pour en juger, il faut notamment tenir compte de la portée de l'atteinte aux droits fondamentaux en cause, de la possibilité d'obtenir ultérieurement, par un contrôle concret de la norme, une protection juridique suffisante, et des circonstances concrètes dans lesquelles ladite norme sera appliquée (arrêt 2C_218/2007 du 9 octobre 2007 consid. 1.5; arrêt 2C_71/2007 du 9 octobre 2007 consid. 2.6; cf. sous l'empire de l'ancien droit, <ref-ruling> consid. 3.2 p. 15; <ref-ruling> consid. 3.1 p. 334/335 et les arrêts cités).
2.2 Un arrêté de portée générale est contraire au principe de l'égalité au sens de l'art. 8 Cst. lorsqu'il établit des distinctions juridiques qui ne se justifient par aucun motif raisonnable au regard de la situation de fait à réglementer ou lorsqu'il omet de faire des distinctions qui s'imposent au vu des circonstances, c'est-à-dire lorsque ce qui est semblable n'est pas traité de manière identique et ce qui est dissemblable ne l'est pas de manière différente; cela suppose que le traitement différent ou semblable injustifié se rapporte à une situation de fait importante (<ref-ruling> consid. 4.2 p. 6-7, 394 consid. 4.2 p. 399; <ref-ruling> consid. 5 et la jurisprudence citée). La question de savoir s'il existe un motif raisonnable pour une distinction peut recevoir des réponses différentes suivant les époques et les idées dominantes. Le législateur dispose toutefois d'un large pouvoir d'appréciation dans le cadre de ces principes et de l'interdiction de l'arbitraire (<ref-ruling> consid. 3.3 p. 254; <ref-ruling> consid. 4.2 p. 7).
2.3 Les motifs de la modification législative ressortent du rapport de février 2005 de la Commission Mesures structurelles, dont la tâche est de trouver des pistes d'économies dans l'administration cantonale. La commission estimait que l'organisation de l'Etat devait pouvoir évoluer dans des délais assez courts. Sa structure devait ainsi être revue et simplifiée notamment par la suppression des petits services et par des regroupements, au terme d'une analyse des prestations, sans devoir attendre le départ à la retraite du titulaire de la fonction pour procéder aux changements souhaités. L'engagement des chefs de service sous contrat de droit privé devait favoriser cette souplesse; les risques de perte d'emploi pouvaient être compensés par les conditions d'engagement. La commission précisait qu'elle n'entendait pas remettre en cause le statut de fonctionnaire dans son ensemble car le droit actuel permettait de déplacer les collaborateurs en fonction des besoins, et de se séparer de ceux qui ne donnaient pas satisfaction (rapport, p. 32). Dans son message, le Conseil d'Etat présente également la suppression du statut de fonctionnaire pour les cadres supérieurs comme une mesure de flexibilisation. Les chefs de service étaient nommés pour quatre ans durant lesquels une résiliation des rapports de services était difficile. Or, les recommandations de la Commission Mesures structurelles comportaient la réorganisation et la fusion de plusieurs services.
2.4 Contrairement à ce que soutiennent les recourants, la modification législative repose ainsi sur des motifs clairs, faisant ressortir la nécessité d'un traitement différencié des cadres supérieurs. La réorganisation des services, et notamment le regroupement de ceux-ci, peut nécessiter la suppression d'un poste de chef de service; en cas d'impossibilité de mettre fin rapidement à la fonction, une restructuration peut se trouver ainsi retardée durant plusieurs années en raison de la situation d'une seule personne. De ce point de vue, la position des chefs de service diffère des autres postes de l'administration, qui peuvent être maintenus sans entraver les remaniements et regroupements de différents services. Cela justifie que l'on renonce aux délais et termes de résiliation prévus dans la LSF, soit en principe (sauf justes motifs) à l'échéance de la période administrative (art. 35 LSF), dont la durée est de quatre ans (art. 5 LSF).
Il n'y a pas non plus d'assimilation insoutenable avec les personnes nommées à titre d'essai; pour ces dernières, la possibilité de mettre fin facilement à l'engagement tient à d'autres raisons: Le temps d'essai (cf., en droit privé, l'<ref-law>) doit permettre de préparer l'établissement de rapports de travail durables et de déterminer si les parties se conviennent mutuellement avant de s'engager pour une plus longue période. Si les rapports contractuels ne répondent pas à leur attente, les parties doivent pouvoir s'en libérer rapidement (<ref-ruling> consid. 7.1.1 p. 111; <ref-ruling> consid. 3.1 p. 125). L'Etat doit ainsi pouvoir renoncer librement à la continuation des rapports de service, afin de permettre l'engagement de personnel répondant au mieux aux exigences du service.
Il n'y a donc pas d'inégalité de traitement de ce point de vue également. Quant au grief d'arbitraire, il n'a pas de portée propre par rapport à celui tiré de l'égalité de traitement; il doit être rejeté dans la même mesure.
3. Invoquant le principe de la proportionnalité, les recourants estiment que la législation actuelle permettrait déjà de garantir la souplesse de l'organisation générale de l'Etat; touchant moins de quarante personnes sur environ 3000 fonctionnaires, la réglementation attaquée ne serait pas propre à atteindre l'objectif poursuivi; le statut de la fonction publique devrait être revu dans son ensemble. Le changement de statut devrait être accompagné de mesures assurant notamment la garantie de l'emploi, la protection contre les licenciements et les garanties de procédure en cas de licenciement, ainsi que des dispositions sur la politique générale du personnel de l'Etat.
3.1 Lorsque, comme en l'espèce, les recourants n'invoquent pas de droit constitutionnel particulier, le Tribunal fédéral n'intervient en cas de violation du principe de la proportionnalité que si la mesure de droit cantonal est manifestement disproportionnée et qu'elle viole simultanément l'interdiction de l'arbitraire (<ref-ruling> consid. 4). En effet, le principe de la proportionnalité, bien que de rang constitutionnel, ne constitue pas un droit constitutionnel avec une portée propre (<ref-ruling> consid. 5b p. 120; <ref-ruling> consid. 2b p. 163). Le grief se confond dès lors avec celui de l'arbitraire (<ref-ruling> consid. 4.1; <ref-ruling> consid. 7a p. 32).
3.2 Comme cela est relevé ci-dessus, l'engagement des chefs de service sous contrat de droit public tend à faciliter, lorsque cela est nécessaire, la résiliation à bref délai des rapports de service. De ce point de vue, la mesure est manifestement propre à atteindre le but visé.
3.3 Les recourants évoquent des "mesures d'accompagnement" qui devraient selon eux assortir le changement de statut. Il apparaît toutefois évident que les dispositions propres à garantir la stabilité de l'emploi et à renforcer la protection contre les licenciements vont à l'encontre du but recherché. De ce point de vue également, les recourants ne parviennent pas à démontrer que le choix opéré par le législateur valaisan serait insoutenable. Les recourants perdent également de vue que les risques accrus de perte d'emploi peuvent être compensés, comme l'a relevé la commission, par des conditions d'engagement plus favorables à d'autres égards, notamment du point de vue salarial, afin de garantir une attractivité suffisante des postes concernés.
4. Les recourants invoquent enfin l'art. 22 de la Constitution valaisanne, aux termes duquel "le fonctionnaire ou l'employé public ne peut être destitué ou révoqué qu'après avoir été entendu ou appelé et sur décision motivée de l'autorité qui l'a nommé". Selon eux, cette disposition impliquerait un droit au renouvellement des rapports de travail. Cela empêcherait des engagements par voie contractuelle et des résiliations sans motifs, et imposerait des décisions susceptibles de recours.
L'argument ne peut être suivi. L'art. 22 Cst./VS rappelle les exigences du droit d'être entendu et de recevoir une décision motivée avant une révocation. Il s'agit là de garanties purement formelles, analogues à celles qui découlent notamment de l'art. 29 al. 2 Cst., et qui continueront à s'appliquer dans le cadre d'un contrat de droit public. Contrairement à ce que soutiennent les recourants, ces garanties formelles sont indépendantes du fond: elles n'impliquent pas qu'une résiliation des rapports de service devrait obligatoirement se fonder sur des motifs particuliers. Quant à la possibilité de recourir, elle demeure puisque l'art. 38 LSF (droit de recours selon la loi sur la procédure et la juridiction administratives) ne fait pas partie des dispositions dont l'application est exclue selon la modification législative.
5. Sur le vu de ce qui précède, le recours en matière de droit public est rejeté. Conformément à l'<ref-law>, les frais judiciaires sont mis à la charge des recourants. Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3000 fr., sont mis à la charge des recourants.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué aux mandataires des recourants et du Grand Conseil du canton du Valais.
Lausanne, le 23 janvier 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Kurz