Faits : A. A._, X._ et Y._ sont les copropriétaires de la vache dénommée Gentiane, appartenant à la race d'Hérens; A.B._ a en propriété la vache Shakira. Le 6 mai 2012, a eu lieu la finale nationale des combats de reines de première catégorie à Aproz (VS). Alors que Gentiane achevait une lutte contre une autre vache, Shakira, voulant les éviter, a battu en retraite. Le jury instauré par la Commission d'organisation des combats de la Fédération suisse d'élevage de la race d'Hérens (ci-après: la Commission d'organisation respectivement la Fédération) a considéré que Shakira avait fui et donc perdu face à Gentiane. A l'issue de la finale précitée, le jury a demandé aux rabatteurs d'attacher Gentiane (ordre exécuté par C._), la déclarant reine. Cette décision, huée par le public, a été notamment contestée par A.B._, son frère B.B._ et D._. Ignorant le tumulte et conformément à la décision du jury, le chef de ring E._ a saisi Gentiane par la sonnette pour la ramener au centre de l'arène en vue de la reprise des sonnettes. D._ s'est alors avancé vers X._ pour le convaincre de laisser détacher Gentiane. Selon les faits retenus, tant X._ que Y._, présents dans l'arène, ont toléré que Gentiane soit détachée par un rabatteur pour qu'elle affronte Shakira, que D._ et les frères B._ ont rapprochée de Gentiane. Sur ordre des rabatteurs, les personnes présentes dans l'arène ont quitté le ring. Après un bref combat, Gentiane a abandonné la lutte et Shakira a été sacrée reine en lieu et place de Gentiane. B. Par trois décisions distinctes du 29 novembre 2012, la Commission d'organisation a prononcé un avertissement contre A._, X._ et Y._ pour non-respect des décisions du jury en raison du détachage de Gentiane, en précisant qu'en cas de récidive sur une période de cinq ans, une sanction sous forme d'exclusion des combats de reines pourra être prononcée (art. 105 al. 2 LTF). Le 20 décembre 2012, les trois intéressés ont recouru contre ces avertissements auprès de la Commission cantonale de recours en matière agricole et de remaniements parcellaires du canton du Valais (ci-après: la Commission de recours), laquelle a, par décision du 13 octobre 2014, partiellement admis le recours, annulé l'avertissement prononcé à l'encontre de A._, absent de l'arène, et confirmé les avertissements frappant X._ et Y._. C. X._ et Y._ forment un recours en matière de droit public au Tribunal fédéral contre la décision du 13 octobre 2014. Ils concluent, sous suite de frais et dépens, à l'admission de leur recours et à la nullité de la décision attaquée. La Commission d'organisation intimée conclut au rejet du recours dans la mesure où il est recevable, sous suite de frais et dépens. La Commission de recours, après avoir obtenu un délai supplémentaire pour se déterminer, y a finalement renoncé. Dans leur réplique du 10 mars 2015, les recourants ont persisté dans les conclusions de leur recours.