Faits: A. La Caisse nationale suisse d'assurance en cas d'accidents (CNA), sise à Lucerne, est un établissement de droit public ayant la personnalité morale. Par acte authentique du 5 mai 2004, instrumenté par Me Valérie Marti, notaire à Genève, la CNA a acquis les parcelles 2571 et 2572, feuille 17, de la commune de Genève/Eaux-Vives, pour le prix de 6'500'000 fr. Par courrier du 13 mai 2004, le notaire prénommé a requis le Conseil d'Etat du canton de Genève d'exonérer la transaction mentionnée ci-dessus des droits de mutation et des émoluments d'inscription au registre foncier. B. Par décision du 23 juin 2004, prise sur délégation du Conseil d'Etat, la Conseillère d'Etat chargée du Département des finances du canton de Genève a rejeté la demande. Elle a considéré que l'art. 80 de la loi fédérale du 6 octobre 2000 sur la partie générale du droit des assurances sociales (LPGA, entrée en vigueur le 1er janvier 2003; RS 830.1) ne prévoyait pas l'exonération des impôts fonciers tels que les « impôts immobiliers sur la valeur brute de l'immeuble et les droits de mutation ». Le 29 juin 2004, le Service de l'enregistrement de l'Administration fiscale du canton de Genève a adressé au notaire prénommé un bordereau de 184'550 fr. 40 au titre des droits de mutation (par 184'500 fr.), autres droits et centimes additionnels afférents à la transaction mentionnée ci-dessus. La CNA et Me Marti ont formé une réclamation à l'encontre de cette taxation. Le 30 juin 2004, le Registre foncier du canton de Genève a facturé à Me Marti pour la transaction en cause des émoluments d'inscription de 18'555 fr. La CNA et Me Marti ont également interjeté une réclamation à l'encontre de cette taxation. C. Agissant par la voie du recours de droit public, la CNA et le notaire prénommé demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler la décision rendue le 23 juin 2004 par la Conseillère d'Etat chargée du Département des finances du canton de Genève. Ils dénoncent une violation de leur droit d'être entendus, la décision entreprise n'étant pas suffisamment motivée, une violation du principe de la force dérogatoire du droit fédéral ainsi qu'une application du droit cantonal contraire au principe d'égalité de traitement et arbitraire. Le Département des finances du canton de Genève conclut au rejet du recours, sous suite de frais. La procédure de réclamation contre le bordereau du 29 juin 2004 et celle ayant pour objet les émoluments du registre foncier ont été suspendues dans l'attente de l'issue de la présente procédure. 