Faits :
A.
En septembre 2013, A._ et B._ ont pris contact avec C._ SA (ci-après: le bureau d'architectes) en vue de construire une villa à Z._.
Par courrier du 30 octobre 2013, le bureau d'architectes leur a confirmé qu'après comparaison avec des projets récents chiffrés, leur souhait de construire une maison pour 1,2 million de francs pouvait être réalisé si le projet ne dépassait pas 250 à 260 m2 (garage non compris); il était précisé que, comme ils étaient au début de leur réflexion, il serait raisonnable d'envisager que la piscine serve de soupape si les coûts devaient excéder l'objectif financier; par ailleurs, C._ SA était prête à réduire ses honoraires de 10% par rapport aux tarifs en vigueur en raison de l'intérêt à travailler avec le couple. L'annexe comportait une proposition d'honoraires avec calcul détaillé. Le coût des prestations à effectuer était estimé selon la norme SIA 102 éd. 2003 avec les coefficients 2011; pour des travaux donnant droit aux honoraires évalués à 900'000 fr., le montant total des honoraires était estimé à 210'000 fr., après la réduction de 10%; la répartition des honoraires selon les prestations à effectuer était le suivant:
- avant-projet 9%
- projet 21%
- autorisation 2,5%
- appel d'offres (plans) 18%
- projet d'exécution 16%
- exécution de l'ouvrage 29%
- documentation ouvrage 4,5%
A une date indéterminée, A._ et B._ ont conclu le contrat d'architecte avec C._ SA.
A un courrier du 3 juin 2014 recommandant aux clients d'engager la phase suivante, le bureau d'architectes a annexé un document qui comportait le coût du projet mis à l'enquête et une nouvelle proposition d'honoraires adaptée à celui-ci. Le coût de réalisation - dont le coût de construction fixé par m3 - était estimé, honoraires compris, à 1'561'855 fr., dont 100'000 fr. pour la piscine. Les honoraires étaient évalués à 265'240 fr., après la réduction consentie de 10%.
La demande de permis de construire a été déposée le 5 juin 2014.
Par courrier du 9 septembre 2014, C._ SA a fait savoir à ses clients, une fois le devis définitif établi, qu'elle s'était montrée trop optimiste dans ses estimations initiales, fondées sur un coût au m3. En effet, évalué d'abord à 1'600'000 fr. avec la piscine, le projet était devisé, après établissement des plans provisoires d'exécution, à 1'950'000 fr. sans la piscine; le respect de cette nouvelle estimation nécessitait encore quelques modifications, en particulier le redimensionnement de la zone d'entrée avec le garage et ses annexes. Le bureau d'architectes expliquait avoir imaginé une enveloppe avec une isolation périphérique et des surfaces vitrées peu importantes, dont le coût se situait à ce qu'il pensait dans la fourchette basse du coût au m3 pour une maison individuelle; le fait de devoir enterrer la maison, l'étendue des façades et l'équipement généreux des espaces intérieurs se révélaient toutefois pénalisants. C._ SA reconnaissait qu'elle aurait peut-être dû être plus prudente dans ses estimations.
A._ et B._ ont tout de suite sollicité un entretien afin de discuter du projet et de son prix.
Par courriel du 15 septembre 2014, ils ont suspendu le projet avec effet immédiat; la solution proposée lors de la rencontre du 10 septembre 2014, pour un budget approximatif de 1'800'000 fr., ne leur convenait pas en raison du prix encore bien trop élevé et du réaménagement non adéquat.
Par courriel du 16 septembre 2014, le bureau d'architectes leur a répondu qu'un projet devait souvent être retravaillé pour diverses raisons et que la situation actuelle n'était pas unique; il reconnaissait néanmoins qu'il aurait dû les avertir déjà en juin, dès que le projet définitif était ficelé; afin d'assumer ses responsabilités, il était prêt à ne pas facturer le travail engagé durant l'été et proposait une nouvelle réunion.
Celle-ci a eu lieu le 5 novembre 2014.
Par lettre du 20 novembre 2014, A._ et B._ ont mis un terme au mandat, faisant valoir que le lien de confiance était rompu. Ils considéraient comme inadmissible la différence entre leur budget de 1,6 million de francs incluant la piscine, connu du bureau d'architectes, et le devis final de 1'955'840 fr. sans piscine ni réserve pour imprévu; ils précisaient que les modifications proposées lors de la dernière rencontre restaient floues et ne permettaient pas d'inverser la tendance au niveau du prix; ils ajoutaient n'avoir toujours pas compris pourquoi le budget communiqué le 9 septembre 2014 ne correspondait pas au projet tel que mis à l'enquête et jugeaient enfin inexploitable le résultat du travail de l'architecte.
Par courrier du 15 décembre 2014, C._ SA a pris acte de la fin du mandat. A bien plaire, elle proposait à A._ et B._ de régler leurs rapports de la manière suivante:
"Nous ne vous faisons pas payer les études liées à l'appel d'offre que nous avons conduites cet été, en revanche, nous vous facturons les études correspondant à la phase de projet qui correspondent à 32,5% des prestations globales. Ce qui représente un montant de 86'203 frs TTC duquel il faut déduire votre acompte de 18'900 frs TTC."
A._ et B._ ont mandaté un autre architecte pour la construction de leur villa à Z._. Le coût de réalisation du nouveau projet, avec piscine, est de 1'663'108 fr.
B.
Par demande du 2 septembre 2015, C._ SA a conclu à la condamnation de A._ et B._ à lui verser la somme de 67'303 fr. (86'203 fr. - 18'900 fr.), plus intérêts à 5% l'an dès le 20 novembre 2014.
A._ et B._ ont conclu au rejet de la demande et, reconventionnellement, à la condamnation de C._ SA à leur payer la somme de 39'272 fr.80, plus intérêts à 5% dès le 15 janvier 2016, à titre de réparation du dommage subi.
Dans le cadre de la procédure probatoire, une expertise a été confiée à une architecte.
Par jugement du 7 mars 2019, le Tribunal civil du Littoral et du Val-de-Travers a condamné A._ et B._ à verser à C._ SA la somme de 61'069 fr.85, plus intérêts à 5% l'an dès le 18 mars 2015 et a rejeté toute autre ou plus ample conclusion.
Par arrêt du 27 septembre 2019, la Cour d'appel civile du Tribunal cantonal neuchâtelois a notamment rejeté l'appel déposé par A._ et B._ et confirmé le jugement de première instance, "au sens des considérants". Les motifs ayant guidé la cour cantonale seront exposés en tant que nécessaire dans la partie "en droit".
C.
A._ et B._ interjettent un recours en matière civile. A titre principal, ils concluent au rejet de la demande principale, à l'admission de la demande reconventionnelle et à la condamnation de C._ SA à leur payer le montant de 39'272 fr.80 avec intérêts à 5% dès le 15 janvier 2016.
C._ SA propose le rejet du recours dans la mesure de sa recevabilité. Le mémoire de réponse était accompagné d'une note d'honoraires du mandataire de l'intimée par 1'969 fr.55.
Les recourants ont encore déposé d'ultimes observations.
Pour sa part, la cour cantonale se réfère aux considérants de son arrêt.

Considérant en droit :
1.
Le recours est dirigé contre un arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par le tribunal supérieur institué comme autorité cantonale de dernière instance, lequel a statué sur recours (<ref-law>). La cause atteint la valeur litigieuse de 30'000 fr. ouvrant le recours en matière civile dans les affaires pécuniaires ne relevant ni du droit du travail, ni du droit du bail à loyer (<ref-law>). Les recourants, dont les conclusions libératoires et reconventionnelles ont été rejetées, ont la qualité pour recourir (<ref-law>). Déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, le recours est en principe recevable, sous réserve de l'examen des griefs particuliers.
2.
2.1. Il n'est pas contesté que les parties étaient liées par un contrat d'architecte global, les prestations à fournir par l'intimée portant non seulement sur la planification, mais également sur la direction des travaux. Selon la jurisprudence, il s'agit d'un contrat mixte, soumis aux règles du mandat ou à celles du contrat d'entreprise selon les prestations de l'architecte en cause (<ref-ruling> consid. 5.1 et 6.2.2; <ref-ruling> consid. 2a p. 545; arrêt 4A_89/2017 du 2 octobre 2017 consid. 4 et les arrêts cités).
Ainsi, lorsque l'architecte fournit des prestations dont il peut garantir le résultat (études préalables, avant-projet, projet, plans, documents de soumission), sa responsabilité relève du contrat d'entreprise (<ref-law>). En revanche, elle ressortit au mandat (<ref-law>) lorsque l'architecte ne s'engage qu'à fournir ses services, promettant toute sa diligence; en particulier, la responsabilité de l'architecte en cas de dépassement de devis ou de défaut de contrôle continu des coûts durant le chantier est soumise aux règles du mandat (arrêt 4A_89/2017 précité consid. 4 et les arrêts cités, consid. 5.1).
Quelle que soit la prestation considérée, les règles du mandat (<ref-law>) s'appliquent à la résiliation du contrat d'architecte global (ATF <ref-ruling> consid. 2a p. 545).
Les parties se sont référées en outre à la norme SIA 102 éd. 2003 (règlement concernant les prestations et honoraires des architectes).
2.2. Les recourants ont résilié le contrat de manière prématurée, après l'établissement du devis, au motif que le lien de confiance avec l'intimée était rompu. Ils faisaient valoir en particulier l'inadéquation entre le projet devisé à 1'955'000 fr., sans réserve pour imprévu, pour une maison sans piscine et leur budget de 1,6 million de francs pour une villa avec piscine.
Le litige porte tout d'abord sur les honoraires du bureau d'architectes pour des prestations qu'il limite à 32,5% des prestations globales, soit pour les phases relatives à l'avant-projet (9%), au projet (21%) et à l'autorisation de construire (2,5%). Sur le fond, les recourants sont d'avis que l'intimée a perdu son droit à toute rémunération en raison de nombreux manquements graves au contrat, rendant ses prestations inutiles et inutilisables.
Par ailleurs, les recourants font valoir qu'en violant son devoir de diligence, l'intimée a engagé sa responsabilité contractuelle et doit réparer le dommage qu'ils ont subi.
3.
Dans un premier moyen fondé sur l'<ref-law>, les recourants demandent au Tribunal fédéral de compléter les constatations de fait de l'autorité précédente en y ajoutant un échange d'e-mails entre les parties d'avril 2014 ainsi que deux courriels des 28 mai 2014 et 3 juin 2014 adressés par l'intimée aux recourants. Invoquant une violation de leur droit d'être entendus, ils exposent que l'état de fait de l'arrêt cantonal laisse supposer qu'il ne s'est rien passé entre octobre 2013 et juin 2014, tandis que les échanges de courriels susmentionnés indiquent que les mandants s'inquiétaient déjà à cette époque de l'absence d'informations sur le coût de leur maison et que l'intimée les avait alors rassurés. Or, les craintes des recourants se seraient finalement révélées exactes, de sorte que l'attitude adoptée alors par l'architecte serait un élément important pour apprécier la diligence dont il a fait preuve dans le cadre de son mandat.
3.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut rectifier ou compléter les constatations de l'autorité précédente que si elles sont manifestement inexactes ou découlent d'une violation du droit au sens de l'<ref-law> (<ref-law>). "Manifestement inexactes" signifie ici "arbitraires" (<ref-ruling> consid. 1.3.1 p. 253; <ref-ruling> consid. 2 p. 117; <ref-ruling> consid. 1.5). Encore faut-il que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>).
La critique de l'état de fait retenu est soumise au principe strict de l'allégation énoncé par l'<ref-law> (<ref-ruling> consid. 2.3 p. 266 et les références). La partie qui entend attaquer les faits constatés par l'autorité précédente doit expliquer clairement et de manière circonstanciée en quoi les conditions précitées seraient réalisées (<ref-ruling> consid. 1.3.1 p. 18 et les références). Si elle souhaite obtenir un complètement de l'état de fait, elle doit aussi démontrer, par des renvois précis aux pièces du dossier, qu'elle a présenté aux autorités précédentes en conformité avec les règles de procédure les faits juridiquement pertinents à cet égard et les moyens de preuve adéquats (<ref-ruling> consid. 2 p. 90). Si la critique ne satisfait pas à ces exigences, les allégations relatives à un état de fait qui s'écarterait de celui de la décision attaquée ne pourront pas être prises en considération (<ref-ruling> consid. 1.3.1 p. 18). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
3.2. Les recourants se réfèrent à des allégués et des pièces précis, conformément aux exigences de motivation du grief. Ils expliquent également en quoi les courriels invoqués sont propres à influer sur le sort du litige.
Dans son courriel du 10 avril 2014 adressé à l'intimée, la recourante écrit: "Nous souhaitons vivement avoir un budget des coûts de notre maison, car nous avons l'impression de naviguer à l'aveugle." Le même jour, l'architecte a répondu par courriel: "Concernant les coûts, nous ne nageons pas à l'aveugle !" Dans son courriel du 28 mai 2014, l'architecte invite les recourants à venir signer les documents du permis de construire le 4 juin 2014. Avec son courriel du 3 juin 2014, il transmet une offre d'honoraires ainsi qu'un coût du bâtiment mis à jour.
Les deux derniers courriels n'apportent rien de déterminant à l'état de fait de l'arrêt cantonal. En effet, l'autorité précédente a constaté que la demande de permis de construire, nécessairement signée par les recourants, avait été déposée le 5 juin 2014. Quant au courriel du 3 juin 2014 et ses annexes, ils font double emploi avec la lettre de l'architecte de la même date, plus détaillée, accompagnée de la proposition d'honoraires avec indication du coût de réalisation de la villa, éléments qui figurent dans la décision entreprise.
En revanche, l'échange de courriels du 10 avril 2014 porte sur des faits qui sont susceptibles d'influer sur le sort du litige, lequel pose la question du respect par l'intimée de ses obligations contractuelles, en particulier en rapport avec les coûts prévisibles de la villa projetée et l'information à fournir aux recourants. Il s'ensuit que la teneur des deux courriels susmentionnés sera intégrée dans l'état de fait déterminant.
4.
Invoquant une violation des art. 394 et 398 CO, les recourants font valoir que les manquements de l'intimée étaient plus nombreux et plus graves que la seule violation du devoir de diligence "sous l'angle du dépassement inacceptable des coûts entre le devis de juin 2014 et celui de septembre 2014", admise par la cour cantonale. En particulier, l'architecte n'aurait pas donné aux mandants toutes les informations nécessaires sur l'évolution des coûts, ni remis un devis général répondant aux exigences de la norme SIA 102 au moment de la signature des plans et du dépôt de la demande de permis de construire en juin 2014. Pour les recourants, la multiplicité et la gravité des manquements commis rendaient inutiles et inutilisables les prestations de l'architecte, qui aurait perdu ainsi tout droit à une rémunération.
4.1. L'art. 1.12.1 du règlement SIA 102 éd. 2003 renvoie au CO pour les suites juridiques d'une fin anticipée du contrat d'architecte. Conformément à l'<ref-law>, le mandat peut être résilié en tout temps. Une résiliation en temps inopportun (cf. <ref-law>) par les recourants n'entrant pas en ligne de compte en l'occurrence, seuls sont en jeu les honoraires de l'architecte pour ses prestations fournies conformément au contrat (cf. art. 1.12.2 1ère phrase in fine du règlement SIA 102 éd. 2003).
4.1.1. Les honoraires de l'architecte sont dus en vertu de l'<ref-law>. Ils sont fixés en première ligne par la convention des parties. En l'espèce, les parties se sont référées au calcul des honoraires d'après le coût de l'ouvrage prévu à l'art. 7 de la norme SIA 102 éd. 2003; les honoraires étaient répartis d'après le pourcentage correspondant à chaque phase des prestations à effectuer (art. 7.9).
4.1.2. Selon l'<ref-law>, applicable en vertu du renvoi de l'<ref-law>, l'architecte doit exécuter avec soin la mission qui lui est confiée et sauvegarder fidèlement les intérêts légitimes de son cocontractant. En particulier, il lui appartient d'informer et de conseiller le mandant, notamment sur les coûts du projet envisagé (arrêt 4A_196/2014 du 1er septembre 2014 consid. 4.1 et les références).
S'il reçoit du mandant une instruction en vertu de laquelle les coûts de la construction ne doivent pas dépasser un certain montant (limite de coût), l'architecte doit veiller à son respect. En particulier, s'il remarque ou doit remarquer que la limite de coût ne pourra pas être tenue ou s'il doute qu'elle puisse l'être, l'architecte doit suspendre immédiatement les travaux, investiguer et informer le mandant de manière à ce que des mesures pour maintenir la limite de coût puissent être prises (arrêt 4A_210/2015 du 2 octobre 2015 consid. 4.3.1 et les références).
4.1.3. S'il viole ses obligations contractuelles, l'architecte peut voir ses honoraires réduits ou même supprimés.
En cas d'exécution défectueuse, le droit du mandataire à des honoraires subsiste, mais le montant des honoraires convenus ( Honorarforderung) peut être réduit pour rétablir l'équilibre des prestations contractuelles. En effet, la rémunération due au mandataire représente une contre-prestation pour l'activité diligente qu'il exerce dans l'affaire dont il est chargé; s'il n'agit pas avec le soin requis, il ne peut donc prétendre, au titre de l'<ref-law> et de la convention des parties, à l'entier des honoraires convenus, c'est-à-dire à la rémunération qui serait équitablement due à un mandataire diligent. Cependant, lorsque les effets du défaut de diligence ont été corrigés et qu'il n'en résulte pas de préjudice pour le mandant, placé dans la même situation qu'en cas d'exécution correcte du mandat, le travail du mandataire doit être honoré (<ref-ruling> consid. 3b p. 425 et les arrêts cités, consid. 4a p. 427; plus récemment, arrêts 4A_444/2019 du 21 avril 2020 consid. 3.2.2, 4A_89/2017 précité consid. 5.2.2).
En revanche, en cas d'inexécution totale, soit lorsque le mandataire demeure inactif ou que ses prestations se révèlent inutiles ou inutilisables ( vollständig unbrauchbar), celui-ci perd son droit à la rémunération (<ref-ruling> consid. 4a p. 127; plus récemment, arrêts 4A_412/2019 du 27 avril 2020 consid. 8.3.1, 4A_444/2019 précité consid. 3.2.1).
4.2.
4.2.1. A titre préalable, il convient d'observer que l'intimée elle-même reconnaît n'avoir droit qu'à des honoraires réduits. En effet, les prétentions qu'elle exerce, portant sur 32,5% de la totalité des prestations, ne correspondent qu'à une partie des prestations exécutées, l'architecte ayant renoncé à réclamer les honoraires liés à l'activité déployée durant l'été 2014.
De même, les honoraires alloués en première instance et confirmés par la cour cantonale résultent d'un calcul qui ne tient pas compte de la part de travail que l'architecte aurait dû refaire si le contrat n'avait pas été résilié.
4.2.2. Examinant la manière dont l'architecte a exécuté son mandat, la cour cantonale retient une violation de l'obligation de diligence. Selon l'arrêt attaqué, l'intimée "n'a pas établi le devis avec toute la diligence requise", respectivement "les plans étaient entachés de défauts", dans la mesure où le coût de réalisation du projet dépassait très largement le coût de 1'561'855 fr. annoncé aux mandants et accepté par eux en juin 2014.
Il y a lieu d'analyser plus précisément le comportement du mandataire relativement au coût du projet qu'il a réalisé pour les recourants.
Selon les faits constatés dans l'arrêt attaqué, le budget des recourants, fixé tout d'abord à 1'200'000 fr., s'élevait finalement à 1'600'000 fr. L'architecte connaissait cette limite de coût, qu'il devait respecter déjà pour le projet dont le concept architectural était discuté avec les mandants. Au stade de la demande d'autorisation de construire en juin 2014, l'intimée a estimé à 1'561'855 fr., piscine comprise, le coût du projet mis à l'enquête, lequel paraissait donc conforme au budget. Il ne s'agissait toutefois pas d'un devis au sens de l'art. 4.32 de la norme SIA 102 éd. 2003, mais plutôt d'une estimation des coûts au sens de l'art. 4.31 de la norme SIA 102 éd. 2003, fondée notamment sur un coût de construction calculé par m3. Établi une fois les plans provisoires d'exécution réalisés, le devis du 9 septembre 2014 - désignant cette fois-ci de manière détaillée les travaux prévus et leurs coûts - aboutit à un coût du projet de 1'955'840 fr., sans la piscine et après quelques modifications, dont un redimensionnement de la zone d'entrée.
Aucune information précise sur les coûts ne ressort de l'état de fait - complété - de l'arrêt attaqué, entre le courrier de l'architecte du 30 octobre 2013, assurant que la maison souhaitée par les recourants pouvait être réalisée pour 1,2 million de francs, et le document du 3 juin 2014, concomitant à la demande d'autorisation de construire, estimant le coût de réalisation du projet à 1'561'855 fr. En particulier, lorsque les intimés ont fait part en avril 2014 de leur impression de naviguer à vue à propos des coûts, l'intimée s'est bornée à les détromper en niant que tel soit le cas.
Pour sa part, l'estimation du 3 juin 2014, portant sur un projet prêt à être mis à l'enquête et comprenant la piscine, était manifestement beaucoup trop basse. En effet, une fois le devis établi après le dépôt de la demande d'autorisation de construire, il s'est avéré, en septembre 2014, que le coût dudit projet, sans la piscine et moyennant encore des modifications, était évalué à 1'955'000 fr., soit un montant de plus de 20% plus élevé que l'estimation précédente et le budget des recourants.
Contrairement à l'avis de la cour cantonale, l'architecte n'a pas violé ses obligations contractuelles en dressant les plans, qui ne sont pas affectés d'erreurs de conception, ou dans le cadre d'un dépassement de devis, les travaux n'ayant pas commencé. L'intimée a bien plutôt méconnu son devoir de diligence en avançant dans le projet, selon les desiderata des mandants et suivant un concept architectural donné, sans évaluer ou sans évaluer correctement son coût à chaque phase de prestations de manière à rester dans le budget qui lui avait été fixé. Par conséquent et en violation de son obligation de fidélité, l'intimée n'a pas non plus informé les recourants, de manière adéquate et en temps voulu, du coût du projet et de son évolution selon les phases en jeu. Ainsi, les recourants n'ont pas disposé d'évaluation des coûts avant le stade du projet déposé pour la demande d'autorisation de construire. Et l'intimée ne leur a alors pas fourni un devis, qui aurait dû en principe être établi à ce moment-là (cf. art. 4.32 et 4.33 de la norme SIA 102 éd. 2003), mais une estimation des coûts normalement effectuée au stade de l'avant-projet (cf. art. 4.31 de la norme SIA 102 éd. 2003).
4.2.3. En définitive, alors que la procédure d'autorisation de construire avait déjà été engagée, les recourants se sont retrouvés avec un projet de villa selon un concept architectural donné, sans la piscine qu'ils souhaitaient, dont le prix devisé dépassait amplement leur budget maximal. Après de vaines discussions avec l'intimée, les mandants ont choisi de renoncer au projet et ainsi de résilier le contrat d'architecte en raison de la rupture du lien de confiance.
Dans la mesure où le coût de la maison envisagée était alors très largement supérieur aux moyens financiers des mandants, force est de constater que le projet de l'intimée ne revêtait plus aucune utilité pour les recourants. Comme cette situation résulte d'une exécution défectueuse du mandat par l'architecte, ce dernier ne peut prétendre à être rémunéré pour ses prestations, conformément à la jurisprudence rappelée au consid. 4.1.3 supra (cf. RAINER SCHUMACHER, Die Haftung des Architekten aus Vertrag, in Das Architektenrecht - Le droit de l'architecte, Gauch/Tercier éd., 3e éd. 1995, n° 605 p. 197, n° 787 p. 252; cf. également YANN FÉROLLES, Le dépassement du devis de l'architecte, 2017, n° 648 p. 190).
4.2.4. Arguant que le défaut de diligence de l'architecte pouvait être réparé en l'occurrence, la cour cantonale a jugé que les mandants devaient rémunérer l'intimée pour ses prestations dès lors qu'ils ne lui avaient pas donné l'occasion de rationaliser le projet pour le faire rentrer dans le budget fixé, ce qui était possible d'après l'expertise.
Selon le passage de l'expertise cité dans l'arrêt attaqué, le projet de l'intimée devait être "rationalisé (surfaces, volumes et géométries générales) " pour que le coût de 1'600'000 fr. puisse être respecté. Il est important de relever que cette conclusion s'inscrit à la suite de l'évocation du nouveau projet des recourants, conforme à leur budget, lequel a été qualifié de "compact" et de "beaucoup plus conventionnel" par l'experte. Or celle-ci avait précisément observé plus haut que, selon le concept choisi par l'intimée, la non-orthogonalité des pièces et les grandes surfaces prévues, même dans une version réduite du projet litigieux, étaient toujours sources de surcoût. C'est dire qu'en réalité la "rationalisation" dont la cour cantonale fait état aurait supposé pour l'intimée de reprendre entièrement le projet, avec un concept architectural totalement différent. Cela confirme qu'au moment de la résiliation du contrat, le travail de l'intimée était bien inutile et inutilisable pour les recourants, contrairement à ce que la cour cantonale a admis.
4.3. En conclusion, le grief tiré d'une violation des art. 394 et 398 CO est fondé. L'intimée ne dispose d'aucune prétention d'honoraires envers les recourants pour les prestations effectuées jusqu'à la résiliation du contrat d'architecte. L'arrêt attaqué sera ainsi réformé en ce sens, d'une part, que la demande de l'intimée en paiement du solde d'honoraires par 67'303 fr. est rejetée et, d'autre part, que l'intimée est condamnée à rembourser aux recourants l'avance versée par 18'900 fr.
5.
Vu l'admission du recours en tant qu'il porte sur le droit à la rémunération de l'intimée, point n'est besoin d'examiner les griefs des recourants soulevés en relation avec le prétendu défaut d'allégation du montant des honoraires.
6.
Dans leur demande reconventionnelle, les recourants invoquent la responsabilité contractuelle de l'architecte et réclament la réparation du dommage résultant de la confiance déçue, à savoir les dépenses qu'ils n'auraient pas engagées si, informés en temps utile du coût réel de la villa, ils avaient renoncé plus tôt au projet.
6.1. Selon l'arrêt attaqué, il s'agit de factures de D._ par 1'404 fr., de E._ SA par 2'637 fr.30, de F._ par 1'436 fr.55, de G._ SA par 2'114 fr.35, du service de l'aménagement du territoire par 150 fr. et de la commune de H._ par 7'040 fr. A ce total de 33'682 fr.20, s'ajoutent des frais d'avocat avant procès par 5'590 fr.60.
La cour cantonale retient tout d'abord que les recourants n'ont pas démontré, pour chaque facture produite, qu'ils auraient pu épargner ces dépenses. Plus loin, elle constate qu'ils ne donnent aucune précision, dans leur appel, permettant de déterminer s'il s'agit réellement de dépenses dues à la mauvaise exécution du mandat; en l'absence de motivation sur ce point (art. 311 al. CPC), le grief est déclaré irrecevable.
S'agissant des honoraires d'avocat avant procès, la cour cantonale les reconstitue en se référant à la décision de première instance et, là également, constate que les recourants, dans leur appel, n'ont pas motivé leur grief à l'encontre du rejet de ce poste du dommage par le premier juge.
6.2. Dans leur mémoire, les recourants affirment que toutes les factures - hormis celle relative aux honoraires avant procès - se rapportent à des dépenses consenties "en vue du projet de l'intimée tel que finalement estimé en juin 2014" et qu'il est évident qu'ils auraient épargné les coûts en question s'ils avaient été dûment informés au printemps 2014 du prix de 1'950'000 fr. du projet, auquel ils auraient alors renoncé. En revanche, le recours ne contient aucun grief dirigé spécifiquement contre l'irrecevabilité, pour défaut de motivation, des griefs de leur appel concernant tant l'existence du dommage que le lien de causalité. Or, lorsqu'une cour cantonale n'entre pas en matière sur un grief en considérant que la motivation est insuffisante, l'examen du Tribunal fédéral ne peut porter que sur la non-entrée en matière. Il s'agit là d'une conséquence de la règle de l'épuisement des instances (BERNARD CORBOZ, in Commentaire de la LTF, 2e éd. 2014, n° 14 ad <ref-law>).
Il s'ensuit que le recours est irrecevable en tant qu'il s'en prend au rejet des conclusions reconventionnelles à concurrence de 20'372 fr.80.
7.
Les recourants obtiennent gain de cause sur environ 4/5 de leurs conclusions. Cette proportion sera appliquée à la répartition des frais et dépens entre les parties (art. 66 al. 1 et art. 68 al. 1 LTF).
La cause sera renvoyée à la cour cantonale pour qu'elle statue à nouveau sur les frais et dépens de la procédure cantonale (art. 67 et 68 al. 5 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis partiellement dans la mesure où il est recevable et l'arrêt attaqué (chiffre 3 du dispositif) est réformé en ce sens que:
- la demande en paiement déposée le 2 septembre 2015
par C._ SA contre A._ et
B._ est rejetée;
- C._ SA est condamnée à payer à A._
et B._, créanciers solidaires, le montant de
18'900 fr. avec intérêts à 5% l'an dès le 15 janvier 2016;
- toute autre ou plus ample conclusion est rejetée.
2.
La cause est renvoyée à la Cour d'appel civile du Tribunal cantonal du canton de Neuchâtel pour nouvelle décision sur les frais et dépens de la procédure cantonale.
3.
Les frais judiciaires, arrêtés à 5'000 fr., sont mis à raison de 4/5 à la charge de l'intimée et à raison de 1/5 à la charge des recourants, débiteurs solidaires.
4.
L'intimée versera aux recourants, créanciers solidaires, une indemnité de 3'600 fr. à titre de dépens réduits.
5.
Le présent arrêt est communiqué aux mandataires des parties et à la Cour d'appel civile du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 13 octobre 2020
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente : Kiss
La Greffière : Godat Zimmermann