Fatti:
A. A.A._, B.A._ e C.A._ sono comproprietari, in regime di proprietà per piani, del mappale xxx di Bissone, su cui è ubicata un'antica abitazione signorile (casa Tencalla). Contigua, sulle particelle yyy e zzz, sorge la casa comunale, eretta sopra un portico con arcate, denominato sottoportico Pusterla, che consente di accedere ad uno spiazzo pubblico prativo in riva al lago Ceresio. I fondi sono assegnati dal piano regolatore comunale alla zona del nucleo tradizionale. Fino agli inizi degli anni novanta, l'area del portico a ridosso di casa Tencalla era occupata da un serbatoio dell'olio combustibile e da due servizi igienici, che ostruivano una porta d'ingresso all'abitazione posta sulla parete di fondo del portico stesso. Nell'ambito dei lavori di ristrutturazione di casa Tencalla è poi stata installata una termopompa, utilizzata anche per l'edificio comunale. Il nuovo impianto ha consentito di smantellare il serbatoio e di arretrare le toilettes, ricollocate a circa un metro di distanza dalla porta dell'abitazione, perpendicolarmente alla medesima, ridandole l'apertura.
B. Il 16 febbraio 2004 il Comune di Bissone ha presentato una domanda di costruzione per sistemare i servizi igienici pubblici, eliminando il vano doccia e mascherando le toilettes mediante la posa di una cornice grigliata perimetrale. Ottenuto il preavviso favorevole dell'autorità cantonale, il 24 giugno 2004 il Municipio ha rilasciato la licenza edilizia e respinto nel contempo l'opposizione interposta da A.A._, B.A._ e C.A._. L'autorità ha in particolare rilevato che i servizi igienici esistevano da decenni e che il loro spostamento era stato concordato con il precedente proprietario di casa Tencalla.
C. Adito dagli opponenti, il Consiglio di Stato ticinese ne ha respinto il ricorso con giudizio del 23 novembre 2004, che, ulteriormente impugnato, è stato confermato dal Tribunale cantonale amministrativo il 7 febbraio 2005. Ritenuta sufficiente la documentazione allegata alla domanda di costruzione, la Corte cantonale ha in sostanza considerato i gabinetti pubblici quale infrastruttura di servizio conforme alle finalità della zona del nucleo. Ha poi giudicato adeguati i provvedimenti previsti per contenere le emissioni moleste degli stessi, muniti di un impianto di aerazione. Anche sotto il profilo delle prescrizioni sullo smaltimento delle acque, sull'inserimento estetico del manufatto e sulle distanze non ha scorto impedimenti al rilascio della licenza. Esente da critiche ha ritenuto infine la valutata sproporzione tra gli inconvenienti connessi all'adozione di misure in favore dei disabili motulesi ed i relativi benefici.
D. Il 10 marzo 2005 A.A._, B.A._ e C.A._ hanno inoltrato dinanzi al Tribunale federale, in un unico atto, un ricorso di diritto amministrativo e un ricorso di diritto pubblico, con cui chiedono essenzialmente l'annullamento della sentenza cantonale. Mediante il ricorso di diritto amministrativo lamentano la violazione del diritto federale in materia ambientale, di protezione delle acque e di tutela dei disabili, oltre a criticare le deduzioni sulla conformità dell'impianto alla destinazione del comparto in cui è inserito. Con il ricorso di diritto pubblico fanno valere, sotto più aspetti, la disattenzione del divieto d'arbitrio e del diritto di essere sentito. Dei motivi si dirà, per quanto necessario, nei considerandi.
E. Senza formulare particolari osservazioni, il Tribunale amministrativo si conferma nella propria decisione, il Consiglio di Stato si rimette al giudizio di questo Tribunale ed il Dipartimento del territorio rinvia al proprio preavviso ed alle risposte presentate in sede cantonale. Il Comune di Bissone chiede che sia il ricorso di diritto amministrativo sia quello di diritto pubblico, quest'ultimo per quanto ammissibile, siano respinti. L'Ufficio federale dell'ambiente, delle foreste e del paesaggio, espressosi sulla questione ambientale, si associa in proposito alle conclusioni della Corte cantonale. In replica i ricorrenti ribadiscono le loro tesi e le domande di giudizio, mentre in duplica l'Autorità comunale si è limitata a produrre un estratto del verbale di una seduta municipale.

Diritto:
1. 1.1 Il ricorso di diritto amministrativo e il ricorso di diritto pubblico sono stati presentati, tempestivamente, con un unico allegato (modalità di per sé legittima, cfr. <ref-ruling> consid. 1.1; <ref-ruling> consid. 1a), sono diretti contro la stessa sentenza e si riferiscono all'identico complesso di fatti. Anche le domande formulate sono del tutto simili. Si giustifica pertanto di trattare i gravami congiuntamente e di pronunciare un unico giudizio (<ref-ruling> consid. 1; <ref-ruling> consid. 1a).
1.2 Il Tribunale federale esamina d'ufficio e con piena cognizione l'ammissibilità dei ricorsi che gli vengono sottoposti, senza essere vincolato, in tale ambito, dagli argomenti delle parti o dalle loro conclusioni (<ref-ruling> consid. 1; <ref-ruling> consid. 1, 353 consid. 1).
2. 2.1 Quando, come in concreto, i ricorrenti agiscono simultaneamente attraverso la via del ricorso di diritto pubblico e quella del ricorso di diritto amministrativo occorre, sulla base della regola della sussidiarietà del ricorso di diritto pubblico enunciata all'art. 84 cpv. 2 OG, esaminare in primo luogo l'ammissibilità del ricorso di diritto amministrativo (<ref-ruling> consid. 1.1; <ref-ruling> consid. 1a; <ref-ruling> consid. 1).
Secondo gli art. 97 e 98 lett. g OG, combinati con l'art. 5 PA, la via del ricorso di diritto amministrativo è aperta contro le decisioni delle autorità cantonali d'ultima istanza fondate sul diritto federale, o che avrebbero dovuto esserlo, sempre che non sia realizzata nessuna delle eccezioni previste agli art. 99 a 102 OG o nella legislazione speciale (<ref-ruling> consid. 1.1; <ref-ruling> consid. 3.1). Il ricorso di diritto amministrativo è pure ammissibile contro le decisioni cantonali fondate nel medesimo tempo sul diritto federale e sul diritto cantonale, in quanto sia in discussione la violazione di norme di diritto federale direttamente applicabili. Per contro, è il rimedio del ricorso di diritto pubblico a essere dato contro decisioni fondate esclusivamente sul diritto cantonale, che non presentano alcuna connessione con l'applicazione del diritto federale (DTF <ref-ruling> consid. 1b/aa; <ref-ruling> consid. 1a/aa; <ref-ruling> consid. 1a; <ref-ruling> consid. 2a). Semplici regole di principio o disposizioni-quadro di diritto pubblico federale, che per essere applicabili nel singolo caso necessitano di misure d'esecuzione di diritto cantonale, non costituiscono di per sé la base per la relativa decisione, la quale non si fonda dunque sul diritto federale. Se il diritto cantonale autonomo viola una regola di principio o una disposizione-quadro di diritto pubblico federale, è data soltanto la via del ricorso di diritto pubblico per violazione della forza derogatoria del diritto federale (DTF <ref-ruling> consid. 1b/aa; <ref-ruling> consid. 1a/aa).
2.2 In concreto, nella misura in cui sono riferite alle pretese emissioni moleste dell'infrastruttura litigiosa, le censure ricorsuali si rapportano all'applicazione del diritto federale sulla protezione dell'ambiente e sono pertanto senza dubbio proponibili mediante ricorso di diritto amministrativo. Tale rimedio è parimenti dato in relazione all'asserita violazione dell'art. 17 della legge federale sulla protezione delle acque, del 24 gennaio 1991 (LPAc; RS 814.20; <ref-ruling> consid. 1; sentenza 1A.24/1993 del 14 dicembre 1993, in: RDAT I-1995 n. 63, consid. 1a; sentenza 1A.160/2005 del 24 ottobre 2005, consid. 1). Laddove invece i ricorrenti sostengono che l'impianto presuppone uno specifico adeguamento pianificatorio e non è conforme alla destinazione della zona di utilizzazione in cui si trova, la sentenza cantonale è impugnabile unicamente con ricorso di diritto pubblico, conformemente al principio sancito dall'art. 34 cpv. 3 della legge federale sulla pianificazione del territorio, del 22 giugno 1979 (LPT; RS 700); ciò vale anche per l'addotta lesione dei disposti pianificatori comunali. Queste critiche concernono infatti il diritto cantonale autonomo e, così come formulate, non sono in relazione sufficientemente stretta con il diritto federale per poter essere sollevate mediante ricorso di diritto amministrativo.
2.3 Resta da esaminare sotto quale profilo vadano trattate le censure dei ricorrenti sull'asserita inagibilità dei servizi igienici in questione per le persone motulese, ritenuto che al riguardo sia la decisione impugnata sia i ricorsi fanno riferimento tanto alla legge federale sull'eliminazione di svantaggi nei confronti dei disabili, del 13 dicembre 2002 (LDis; RS 151.3), quanto all'art. 30 della legge edilizia ticinese, del 13 marzo 1991 (LE; cfr. BU/TI 1993 1, per il testo originale della norma, e BU/TI 2005 15, per la modifica valida dal 1° febbraio 2005).
2.3.1 La legge sui disabili, entrata in vigore il 1° gennaio 2004, si fonda sul divieto di discriminazione sancito dall'art. 8 cpv. 2 Cost. e sul mandato legislativo dell'art. 8 cpv. 4 Cost., secondo cui la legge prevede provvedimenti per eliminare gli svantaggi nei confronti dei disabili. Oltre che, tra l'altro, in materia di trasporti pubblici e di formazione, la normativa si applica anche alle costruzioni e agli impianti accessibili al pubblico per i quali un'autorizzazione a costruire o ad effettuare lavori di rinnovo è accordata dopo la sua entrata in vigore (art. 3 lett. a LDis), come è il caso nella fattispecie. Essa impone a Confederazione e Cantoni di adottare provvedimenti per impedire, ridurre o eliminare gli svantaggi (art. 5 cpv. 1 LDis), precisando nel contempo i criteri che permettono di prescindere dall'adozione di simili misure per ragioni di proporzionalità (art. 11 e 12 LDis) e riservando in generale ai Cantoni la facoltà di adottare disposizioni più favorevoli (art. 4 LDis).
2.3.2 Le menzionate disposizioni concernenti l'eliminazione delle barriere architettoniche hanno sollevato critiche sotto il profilo della loro costituzionalità, poiché regolamenterebbero essenzialmente questioni di pertinenza dei Cantoni (Yvo Hangartner, Grundrechtliche Gesetzgebungsaufträge und bundesstaatliche Kompetenzordnung, in: AJP 2001 pag. 476 segg., in part. pag. 479; cfr. anche l'intervento del Consigliere nazionale Loepfe, in: BU/CN 2004, pag. 905). Questi dispongono infatti di una competenza generale ed originaria in materia edilizia (Peter Hänni, Planungs-, Bau- und besonderes Umweltschutzrecht, 4a ed., Berna 2002, pag. 11; cfr. pure l'art. 75 Cost.). In realtà, la disciplina legislativa rispetta tuttavia il principio secondo cui la garanzia federale di un diritto fondamentale, quale l'art. 8 cpv. 2 Cost., non conferisce di massima nuove competenze alla Confederazione (Ulrich Häfelin/ Walter Haller, Schweizerisches Bundesstaatsrecht, 6a ed., Zurigo 2005, n. 1070), che del resto non possono incontestabilmente venir dedotte nemmeno dall'art. 8 cpv. 4 Cost. (Hangartner, op. cit., pag. 478; Adriano Previtali, Behindertengerechtes Bauen, in: BR 2/2001 pag. 47 segg., in part. pag. 53).
In sostanza, le norme legali si limitano a precisare il contenuto del diritto fondamentale che vieta la discriminazione delle persone disabili, definendo in maniera più puntuale le nozioni di disabile e di svantaggio (art. 2 LDis) e concretizzando le stesse in funzione dei diversi ambiti di applicazione (art. 3 LDis; Previtali, loc. cit.). Tali disposti, che si prefiggono di creare le condizioni quadro affinché dette persone possano partecipare più attivamente alla vita della società (art. 1 cpv. 2 LDis), lasciano ai Cantoni le loro facoltà originarie di stabilire regole concrete conformi alla garanzia costituzionale. In altri termini, la legge sui disabili non contiene disposti di diritto edilizio materiale (federale), ma fissa requisiti generali che, nel rispetto della ripartizione usuale delle competenze, riservano l'adozione di specifiche norme di polizia delle costruzioni di diritto cantonale (Messaggio relativo alla LDis, dell'11 dicembre 2000, in: FF 2001 pag. 1477 segg., in part. n. 8.1.1 pag. 1575-1576; Previtali, op. cit., pag. 53-54; idem, Le recenti innovazioni della normativa federale sulle persone disabili, in: Marco Borghi [a cura di], L'autonomia del disabile nel diritto svizzero, Bellinzona 2004, pag. 153 segg., in part. pag. 171-172; cfr. anche l'intervento della Consigliera federale Metzler, in: BU/CS 2002 pag. 713; in parte divergente: Nadja Herz, Behindertengleichstellungsgesetz - Auswirkungen auf das Bauen, in: PBG Aktuell 3/2004 pag. 5 segg., in part. pag. 11). Prova ne sia che solo per le costruzioni della Confederazione o da questa sussidiate la legge prevede norme specifiche più dettagliate, rinviando altresì a regole tecniche di natura materiale (cfr. l'art. 15 cpv. 2 LDis e l'art. 8 della relativa ordinanza, del 19 novembre 2003 [ODis; RS 151.31]).
2.3.3 Ne discende che sull'aspetto dell'eliminazione delle barriere architettoniche negli edifici, esclusi i casi in cui si tratta di stabili costruiti o sussidiati dalla Confederazione, il diritto federale si limita a porre delle regole di principio e delle disposizioni-quadro, che, per essere applicabili in un caso concreto, necessitano di misure legislative d'esecuzione di diritto cantonale. I rimproveri che i ricorrenti muovono a questo proposito alla sentenza impugnata possono pertanto essere esaminati solo nel contesto di un ricorso di diritto pubblico.
3. 3.1 Limitatamente alle censure precedentemente indicate (cfr. consid. 2.2), il ricorso di diritto amministrativo è senza dubbio ammissibile sotto il profilo degli art. 97 segg. OG. In particolare, data la diretta vicinanza della loro proprietà all'installazione controversa, i ricorrenti sono toccati in maniera diretta dalla decisione impugnata ed hanno un interesse perlomeno fattuale degno di protezione al suo annullamento. Essi sono pertanto legittimati a ricorrere ai sensi dell'art. 103 lett. a OG.
3.2 Con il ricorso di diritto amministrativo può essere fatta valere la violazione del diritto federale, compreso l'eccesso o l'abuso del potere di apprezzamento (art. 104 lett. a OG). Quando, come in concreto, la decisione impugnata emana da un'autorità giudiziaria, l'accertamento dei fatti da essa operato vincola il Tribunale federale, salvo che questi risultino manifestamente inesatti o incompleti oppure siano stati appurati violando norme essenziali di procedura (art. 105 cpv. 2 OG). Nell'ambito di questo rimedio il giudice amministrativo federale può essere adito anche con censure relative alla violazione di diritti costituzionali dei cittadini, che pure rientrano nella nozione di diritto federale ai sensi dell'art. 104 lett. a OG (<ref-ruling> consid. 3; <ref-ruling> consid. 3).
4. Ripetutamente nel loro gravame, e pure in relazione alla protezione dell'ambiente, i ricorrenti rimproverano alla Corte cantonale di aver violato il loro diritto di essere sentiti, ignorando o non motivando a sufficienza la reiezione di determinate censure, e rifiutandosi di esperire un sopralluogo.
La censura dev'essere esaminata in primo luogo, siccome il diritto di essere sentito, sancito dall'art. 29 cpv. 2 Cost., ha natura formale e la sua lesione comporta di regola l'annullamento della decisione impugnata indipendentemente dall'eventuale fondatezza del gravame nel merito (<ref-ruling> consid. 4d; <ref-ruling> consid. 3d/aa).
4.1 Il diritto di essere sentito comprende vari aspetti, tra cui, effettivamente, quello di ottenere una decisione motivata (<ref-ruling> consid. 3.2). L'esigenza della motivazione ha essenzialmente lo scopo di permettere alle parti interessate di rendersi conto della portata del provvedimento e di poterlo se del caso impugnare con cognizione di causa. Ciò non significa che l'autorità sia tenuta a pronunciarsi in modo esplicito ed esaustivo su tutte le argomentazioni addotte; essa può in effetti occuparsi delle sole circostanze rilevanti per il giudizio, atte ad influire sulla decisione di merito (<ref-ruling> consid. 3.2; <ref-ruling> consid. 2b, 15 consid. 2a/aa; <ref-ruling> consid. 2c).
Nella fattispecie, le considerazioni sviluppate dai giudici cantonali risultano nel loro complesso senza dubbio sufficientemente circostanziate per permettere di comprendere appieno la portata della sentenza impugnata, come lo dimostrano del resto le articolate impugnative inoltrate in questa sede. La Corte cantonale si è confrontata con tutti i punti essenziali del ricorso, non pronunciandosi semmai in maniera espressa soltanto su aspetti riconoscibili come irrilevanti e comunque appena accennati anche dai ricorrenti stessi. In particolare, neppure sulla questione della preesistenza dal profilo giuridico dei servizi igienici la motivazione presta il fianco a critiche. Alle obiezioni sulla mancanza di una valida licenza edilizia per l'attuale installazione, il Tribunale amministrativo ha sostanzialmente opposto che la struttura potrebbe venir autorizzata anche se nuova: la questione risultava quindi priva di portata concreta ai fini del giudizio. In tale ottica va parimenti trattata in questa sede.
4.2 Il diritto di essere sentito comprende pure la facoltà per l'interessato di consultare gli atti del procedimento, di offrire mezzi di prova su punti rilevanti e di partecipare alla loro assunzione o perlomeno di potersi esprimere sui risultati in quanto possano influire sul giudizio (<ref-ruling> consid. 2a/aa e rinvii). Tale diritto non impedisce tuttavia all'autorità di procedere ad un apprezzamento anticipato delle prove richieste, se è convinta ch'esse non potrebbero condurla a modificare la sua opinione (<ref-ruling> consid. 4a; <ref-ruling> consid. 4a). In tale ambito spetta all'autorità un vasto margine di valutazione e la censura di violazione del diritto di essere sentito coincide con la critica di apprezzamento arbitrario delle prove (<ref-ruling> consid. 4a).
Al riguardo, i piani allegati alla domanda di costruzione e le fotografie prodotte dalle parti consentono di allestire un quadro preciso e concreto della situazione attuale dei luoghi della contestazione e dei lavori previsti. La rinuncia dei giudici cantonali ad esperire il sopralluogo richiesto, in quanto non avrebbe portato alla conoscenza di ulteriori fatti rilevanti per il giudizio, non appare dunque lesiva della Costituzione. Certo, l'ispezione locale avrebbe verosimilmente permesso di chiarire la controversia sull'effettiva esistenza di un impianto di aerazione, ammessa dal Tribunale amministrativo, ma invero non confermata dall'autorità municipale, se non rilevando come la struttura sia dotata di un sistema di ventilazione naturale. Come meglio indicato nel seguito, anche se manifestamente inesatto, questo accertamento non risulterebbe comunque di decisivo rilievo. Per gli stessi motivi, non appare necessario né si giustifica di esperire un sopralluogo in questa sede (art. 95 OG; <ref-ruling> consid. 2a; <ref-ruling> consid. 1d).
5. Dal profilo del diritto sulla protezione dell'ambiente, i ricorrenti sostengono che l'esigenza di limitare le emissioni moleste sarebbe stata del tutto trascurata, salvo considerare, in maniera manifestamente inesatta, che i gabinetti sono già muniti di un impianto di aerazione.
5.1 La legge federale sulla protezione dell'ambiente, del 7 ottobre 1983 (LPAmb; RS 814.01), ha come scopo, tra l'altro, la protezione dell'uomo, della fauna e della flora dagli effetti dannosi e molesti (art. 1 cpv. 1 LPAmb). Tra questi effetti vi sono gli inquinamenti atmosferici dovuti alla costruzione o all'esercizio di impianti, ossia le alterazioni delle condizioni naturali dell'aria dovute segnatamente anche ad odori (art. 7 cpv. 1, 3 e 7 LPAmb; cfr. anche gli art. 1 cpv. 1 e 2 cpv. 1 dell'ordinanza contro l'inquinamento atmosferico, del 16 dicembre 1985 [OIAt; RS 814.318.142.1]). Gli inquinamenti atmosferici vanno innanzitutto limitati mediante misure applicate alla fonte (limitazione delle emissioni; art. 11 cpv. 1 LPAmb). Laddove, come nel caso degli odori, non esistono dei valori limite delle emissioni, l'autorità limita preventivamente queste ultime nella misura massima consentita dal punto di vista tecnico, delle condizioni d'esercizio e dalle possibilità economiche (art. 11 cpv. 2 LPAmb; art. 4 cpv. 1 OIAt).
5.2 Il Tribunale federale ha avuto modo di occuparsi di inquinamento atmosferico sotto forma di odore soprattutto nel caso di impianti in cui l'effetto sgradevole era indubbiamente di una certa intensità e chiaramente percettibile: infrastrutture per la detenzione e l'allevamento di animali (sentenza 1A.58/2001 del 12 novembre 2001, in: RDAF 2003 I pag. 524; sentenza 1A.225/1995 del 9 settembre 1997, in: RDAF 1998 I pag. 352), in particolare maiali (<ref-ruling>; <ref-ruling>; sentenza 1A.108/2004 del 17 novembre 2004, in: URP 2005 pag. 243), fosse per il colaticcio (<ref-ruling>; sentenza 1A.70/2001 del 3 ottobre 2001, in: RDAT I-2002 n. 68), centri per il compostaggio (sentenza 1A.92/1998 del 30 dicembre 1998, in: RDAF 1999 I pag. 410) o ancora nel caso di un deposito per la conservazione di alcune decine di tonnellate di formaggio (sentenza 1A.46/2003 del 2 settembre 2003).
Comparando questi casi alle immissioni che possono generalmente provenire da un modesto impianto sanitario pubblico dotato di due sole toilettes, ci si potrebbe invero chiedere se la struttura litigiosa ricada effettivamente nel campo d'applicazione della legislazione di protezione dell'ambiente. In effetti, non ogni alterazione di breve durata delle condizioni naturali dell'aria rappresenta un inquinamento atmosferico; l'effetto sullo stato dell'aria deve piuttosto essere percepibile per una durata più lunga, che ne consenta anche la misurazione (sentenza 1A.288/1995 del 19 novembre 1996, in: URP 1997 pag. 213, consid. 3b/aa; Keller, Kommentar zum Umweltschutzgesetz, 2a ed., Zurigo 2002, n. 16 ad art. 7; cfr. anche Messaggio concernente la LPAmb, del 31 ottobre 1979, in: FF 1979 pag. 713 segg., in part. pag. 749).
5.3 In ogni caso, occorre tener presente che il principio di prevenzione di cui all'art. 11 LPAmb tende alla riduzione e non alla soppressione delle emissioni e che, da questo profilo, disturbi di intensità minima vanno presi in conto e tollerati (<ref-ruling> consid. 4c/bb; <ref-ruling> consid. 4a). Nello stesso senso la giurisprudenza considera che se le emissioni prevedibili di un impianto sono suscettibili di provocare effetti contenuti e di poca importanza, non vi siano ragioni per adottare particolari provvedimenti a fini preventivi: in "casi-bagatella" dal profilo ambientale l'art. 11 cpv. 2 LPAmb non trova dunque applicazione (<ref-ruling> consid. 8b; <ref-ruling> consid. 6c; Jacques Meyer, La protection du voisin contre les nuisances: choisir entre la voie civile et la voie administrative, in: URP 2001 pag. 411 segg., in part. pag. 422; Alexander Zürcher, Die vorsorgliche Emissionsbegrenzung nach dem Umweltschutzgesetz, tesi Basilea 1995, pag. 254).
Ora, per quanto il controverso impianto possa apparire indesiderato ai ricorrenti, l'uso che se ne può ragionevolmente attendere è assai ridotto, non solo per il tipo e la grandezza dell'infrastruttura, ma soprattutto perché è legato essenzialmente all'utilizzo dell'antistante spiaggetta pubblica nei mesi estivi. Ritenuto che il Comune provvederà alla manutenzione ed alla pulizia regolare dei servizi igienici, com'è prevedibile e peraltro nel suo stesso interesse, le emissioni che possono derivarne sono del tutto limitate ed atte a disperdersi impercettibilmente e rapidamente nell'ambiente. Considerata la circolazione naturale dell'aria di cui possono beneficiare le toilettes grazie alle loro aperture, l'adozione di particolari provvedimenti per ridurre le emissioni, come ad esempio l'installazione di un impianto di aerazione, non appare esigibile per ragioni di proporzionalità, poiché non permetterebbe con ogni probabilità alcuna significativa riduzione del preteso inquinamento atmosferico. Si è invero in presenza di un caso-bagatella, per il quale la portata dell'art. 11 cpv. 2 LPAmb risulta limitata. Va d'altronde rilevato che l'intervento previsto, consistente anche nella schermatura almeno parziale delle entrate dei gabinetti, ridurrà comunque gli altri disagi lamentati dai ricorrenti, di natura non tanto ambientale, quanto piuttosto estetica.
5.4 Sulla base delle considerazioni esposte, sotto il profilo della legislazione di protezione dell'ambiente non sono pertanto ravvisabili ragioni per impedire il rilascio della controversa licenza edilizia o per imporre misure specifiche a titolo preventivo.
6. I ricorrenti rimproverano ai giudici cantonali di aver ritenuto che i servizi igienici sono allacciati alle canalizzazioni senza esperire alcuna verifica. In tal modo essi avrebbero violato l'art. 17LPAc, secondo cui il rilascio della licenza edilizia è sostanzialmente subordinato alla garanzia che le acque di scarico inquinate siano immesse nelle canalizzazioni (art. 17 lett. a LPAc).
Così come esposta, la censura è di per sé nuova. In sede cantonale gli insorgenti si sono infatti limitati ad eccepire l'incompletezza formale degli atti per l'assenza del piano delle canalizzazioni, senza tuttavia pretendere che i servizi non saranno raccordati alla rete delle acque luride. Benché, proprio per questa ragione, detto aspetto non è stato esaminato in maniera particolareggiata in precedenza, non vi è alcun motivo per dubitare dell'esattezza dei fatti accertati dall'istanza inferiore, che non possono venir considerati manifestamente inesatti e risultano dunque vincolanti per il Tribunale federale (art. 105 cpv. 2 OG). Premesso che il preavviso cantonale subordina espressamente il rilascio della licenza edilizia all'allacciamento alle canalizzazioni, il Municipio ha infatti confermato che già la struttura esistente è collegata alle tubazioni della casa comunale. I gabinetti pubblici sono d'altronde stati spostati nella loro collocazione attuale una decina di anni orsono, nell'ambito di importanti lavori di ristrutturazione della casa comunale e di casa Tencalla; non è quindi seriamente ipotizzabile che perlomeno in quell'occasione non siano stati raccordati alla rete delle canalizzazioni e che scarichino (ancora) le acque luride direttamente nel lago Ceresio, come paventano i ricorrenti. Nemmeno su questo punto il gravame può quindi trovare accoglimento.
7. Per quanto concerne il ricorso di diritto pubblico, l'impugnativa è di massima ammissibile sotto il profilo degli art. 84 cpv. 1 lett. a e 86 cpv. 1 OG, siccome rivolta contro una decisione finale di ultima istanza cantonale e fondata essenzialmente su una pretesa violazione dei diritti costituzionali dei cittadini.
7.1 Secondo l'art. 88 OG, il vicino è legittimato ad interporre ricorso di diritto pubblico contro il rilascio di una licenza edilizia solo se invoca la violazione di disposizioni destinate a proteggere non soltanto l'interesse pubblico, ma anche quello proprio dei vicini, come è segnatamente il caso per le norme concernenti le dimensioni, le distanze dai confini, l'indice di sfruttamento, l'altezza e il numero dei piani degli edifici o ancora, di principio, il tipo e l'intensità dell'utilizzazione ammissibile dei fondi (<ref-ruling> consid. 2c-d; <ref-ruling> consid. 1b; <ref-ruling> consid. 3b). Il vicino deve inoltre rientrare nell'ambito di protezione di queste disposizioni ed essere toccato dai pretesi effetti illeciti della costruzione litigiosa (<ref-ruling> consid. 1a).
Nella misura in cui sostengono che i servizi igienici sarebbero incompatibili con la destinazione della zona di piano regolatore, viste le ripercussioni moleste che potrebbero ingenerare, i ricorrenti si richiamano a precetti che appaiono di per sé funzionali anche ai loro propri interessi. Al riguardo, la loro legittimazione può pertanto essere ammessa, così com'è il caso in relazione alle censure concernenti il mancato rispetto delle distanze. Per contro, essi non sono legittimati a criticare il progetto dal punto di vista dell'estetica, in quanto le relative disposizioni sono destinate essenzialmente a tutelare l'interesse pubblico (<ref-ruling> consid. 1b; <ref-ruling> consid. 1b).
Essi non fanno valere di utilizzare tale impianto né tanto meno di ricadere nell'ambito di protezione delle norme federali o cantonali sulle misure in favore dei disabili, che mirano specificatamente a tutelare questa categoria di persone. Soltanto ad un disabile è peraltro riconosciuto il diritto soggettivo di chiedere, nell'ambito di una procedura edilizia, che si rinunci ad uno svantaggio ai sensi della legge nella realizzazione di una costruzione o di un impianto (art. 7 cpv. 1 LDis). Anche su questo aspetto il gravame è pertanto inammissibile.
7.2 Secondo l'art. 90 cpv. 1 lett. b OG, l'atto di ricorso deve contenere l'esposizione dei fatti essenziali e quella concisa dei diritti costituzionali o delle norme giuridiche che si pretendono violati, specificando in cosa consista la violazione. Nell'ambito di un ricorso di diritto pubblico, il Tribunale federale non applica quindi d'ufficio il diritto, ma statuisce unicamente sulle censure sollevate dall'insorgente e solo se le stesse sono sufficientemente sostanziate (<ref-ruling> consid. 2.1; <ref-ruling> consid. 4; <ref-ruling> consid. 1.6, 113 consid. 2.1). Già di primo acchito le descritte esigenze di motivazione non appaiono soddisfatte laddove i ricorrenti, come del resto in sede cantonale, si limitano ad accennare alla violazione di disposti della legislazione sanitaria cantonale e di norme tecniche in materia di sicurezza ed igiene. Lo stesso dicasi per la lamentata incompletezza degli atti allegati alla domanda di costruzione: i ricorrenti non spiegano infatti in che modo l'assenza di alcune indicazioni puntuali avrebbe impedito loro di comprendere veramente la portata dei lavori progettati.
8. A giudizio dei ricorrenti sarebbe arbitrario considerare i gabinetti pubblici conformi alle finalità del comparto del nucleo tradizionale, riservato di principio alla residenza, già in ragione dei loro rilevanti effetti molesti. Ritenuto che l'impianto servirebbe in realtà a coloro che usufruiscono del giardino pubblico esistente tra casa Tencalla ed il lago, esso andrebbe peraltro previsto nell'ambito di una modifica del piano regolatore, che istituisca una zona specificatamente qualificata come area pubblica.
8.1 Al riguardo, la Corte cantonale ha rilevato che le norme di attuazione del piano regolatore (NAPR) di Bissone non determinano in maniera specifica l'utilizzazione ammissibile dei fondi nella zona del nucleo del villaggio, fondando comunque sul presupposto che sia possibile l'insediamento tradizionale di abitazioni e di attività mercantili ed artigianali con modeste ripercussioni ambientali. Ha quindi ritenuto che le controverse toilettes si integrino funzionalmente in tale contesto, rispondendo alle esigenze dei frequentatori della zona del nucleo.
A non averne dubbi, tale conclusione non risulta manifestamente insostenibile, gravemente lesiva di una norma o di un chiaro principio giuridico o in contrasto intollerabile con il sentimento di giustizia e di equità: essa non integra pertanto gli estremi dell'arbitrio (<ref-ruling> consid. 2.1; <ref-ruling> consid. 3.1, 49 consid. 4, 8 consid. 2.1). In effetti, non è di per sé fuori luogo ammettere che due servizi igienici pubblici servano ai fruitori, in generale, di qualsiasi zona edificabile; tanto meno è errato riconoscerlo in relazione al comparto del nucleo di Bissone, caratterizzato notoriamente anche da un'importante frequentazione turistica. Inoltre, come già esposto nell'ottica della protezione dell'ambiente (consid. 5.3), le immissioni moleste che ne potrebbero derivare sono del tutto contenute e dunque certamente compatibili con le necessità derivanti dalla funzione residenziale.
8.2 Non occorre peraltro chiedersi se il controverso impianto abbia un'incidenza territoriale tanto importante da richiedere una preventiva modifica del piano regolatore, anziché soggiacere semplicemente alla procedura della domanda di costruzione: la questione dell'obbligo di pianificazione si pone infatti unicamente per edifici ed impianti ubicati fuori della zona edificabile (<ref-ruling> consid. 4d; sentenza 1A.71/2000 del 3 gennaio 2001, in: RDAT II-2001 n. 66, consid. 5; Hänni, op. cit., pag. 105, n. 188). Anche su questo aspetto le censure ricorsuali vanno quindi respinte.
9. In merito al problema delle distanze, i ricorrenti rimproverano alla Corte cantonale di non essersi sostanzialmente espressa sulla disattenzione di alcune norme invocate e di aver in tal modo violato il loro diritto di essere sentiti. Ritengono inoltre infondato l'accertamento secondo cui i gabinetti verrebbero inseriti all'interno di uno stabile esistente e reputano arbitraria l'interpretazione dei disposti che reggono la costruzione di latrine in prossimità di fondi altrui.
9.1 Sulle distanze nella zona del nucleo, l'art. 10.1 NAPR dichiara applicabile l'ordinamento della legge cantonale di applicazione e complemento del codice civile svizzero, del 18 aprile 1911 (LAC). Secondo il Tribunale amministrativo, nella fattispecie non si porrebbe tuttavia alcun problema di distanze tra edifici o dal confine, perché la costruzione in cui sono previste le toilettes è contigua allo stabile di proprietà dei ricorrenti e la contiguità è espressamente ammessa dall'art. 10.1 NAPR. Con tale argomentazione i giudici cantonali hanno in pratica confutato, in maniera generale ed invero nemmeno troppo indiretta, le critiche sul mancato rispetto delle distanze previste dalle disposizioni a cui si richiamavano i ricorrenti, segnatamente gli art. 6 NAPR e 124 LAC. Nel suo complesso, anche su questo punto, la motivazione del giudizio impugnato risulta quindi sufficiente e rispettosa dell'obbligo imposto dall'art. 29 cpv. 2 Cost. (cfr. anche consid. 4.1).
9.2 Gli insorgenti non contestano peraltro l'assunto della Corte cantonale, ossia l'esistenza di una situazione di contiguità e la conseguente irrilevanza del regime sulle distanze. Non compete quindi al Tribunale federale verificare d'ufficio l'esattezza di tale accertamento e determinarne le eventuali implicazioni giuridiche (art. 90 cpv. 1 lett. b OG; cfr. consid. 7.2). I ricorrenti non spiegano nemmeno in che misura sarebbe decisivo stabilire se i gabinetti siano previsti all'interno o all'esterno di un edificio. Tuttavia soltanto deducendo da tale assunto delle conseguenze giuridiche la decisione potrebbe semmai risultare arbitraria non solo nella sua motivazione, ma anche nel risultato (<ref-ruling> consid. 2.1; <ref-ruling> consid. 3.1). In ogni caso, se non è errato ritenere che le toilettes saranno ubicate all'esterno, siccome vi si accederebbe direttamente dall'area pubblica e non dalla casa comunale, è altresì quantomeno sostenibile affermare che saranno situate all'interno del complesso dello stabile amministrativo e del perimetro che questo già occupa.
9.3 Non può infine venir ravvisato l'arbitrio nemmeno nell'interpretazione operata dal Tribunale amministrativo degli art. 112 e 113 LAC, secondo cui la costruzione di una latrina deve avvenire ad una distanza di almeno tre metri da una proprietà altrui, salvo eccezione concessa dal pretore se i lavori sono fatti a regola d'arte, con materiali appropriati ed in modo da escludere qualsiasi nocumento al vicino. Innanzitutto va osservato che queste norme, riprese nella LAC, risalgono sostanzialmente alla prima metà del diciannovesimo secolo, quando gli impianti sanitari non erano certo comparabili a quelli odierni (Adelio Scolari, Commentario LALPT, LE e LAC, Bellinzona 1996, n. 1425). In secondo luogo, non appare del tutto privo di fondamento attribuire, per analogia, le competenze del giudice civile di prime cure al Municipio, ossia all'autorità di prima istanza in materia edilizia, quando le norme della LAC vengono adottate a titolo di disposti pianificatori comunali. Non risulta infatti arbitrario intendere il rinvio alla LAC come limitato alle sole norme materiali sulle distanze, senza conseguenze sulla competenza delle autorità chiamate ad applicare tali norme in ambito edilizio. Per le ragioni sostanzialmente già indicate nei considerandi precedenti, la Corte cantonale poteva poi, a mente dell'art. 113 LAC, legittimamente ritenere adempiute le condizioni per derogare alla distanza prevista (cfr. anche Scolari, loc. cit.).
9.3 Non può infine venir ravvisato l'arbitrio nemmeno nell'interpretazione operata dal Tribunale amministrativo degli art. 112 e 113 LAC, secondo cui la costruzione di una latrina deve avvenire ad una distanza di almeno tre metri da una proprietà altrui, salvo eccezione concessa dal pretore se i lavori sono fatti a regola d'arte, con materiali appropriati ed in modo da escludere qualsiasi nocumento al vicino. Innanzitutto va osservato che queste norme, riprese nella LAC, risalgono sostanzialmente alla prima metà del diciannovesimo secolo, quando gli impianti sanitari non erano certo comparabili a quelli odierni (Adelio Scolari, Commentario LALPT, LE e LAC, Bellinzona 1996, n. 1425). In secondo luogo, non appare del tutto privo di fondamento attribuire, per analogia, le competenze del giudice civile di prime cure al Municipio, ossia all'autorità di prima istanza in materia edilizia, quando le norme della LAC vengono adottate a titolo di disposti pianificatori comunali. Non risulta infatti arbitrario intendere il rinvio alla LAC come limitato alle sole norme materiali sulle distanze, senza conseguenze sulla competenza delle autorità chiamate ad applicare tali norme in ambito edilizio. Per le ragioni sostanzialmente già indicate nei considerandi precedenti, la Corte cantonale poteva poi, a mente dell'art. 113 LAC, legittimamente ritenere adempiute le condizioni per derogare alla distanza prevista (cfr. anche Scolari, loc. cit.).
10. 10.1 Sulla base delle considerazioni esposte, sia il ricorso di diritto amministrativo sia quello di diritto pubblico, quest'ultimo nella misura della sua ammissibilità, vanno pertanto respinti.
10.2 Le spese processuali vanno poste in maniera complessiva a carico dei ricorrenti, in solido, secondo soccombenza (art. 156 cpv. 1 e 7, 153 e 153a OG). La tassa di giustizia non soggiace peraltro alla limitazione dell'art. 10 cpv. 3 LDis, dal momento che gli insorgenti non adempiono i requisiti per potersi prevalere della menzionata legge federale. Al Comune di Bissone, che si è fatto assistere da un avvocato siccome privo di un servizio giuridico proprio, va inoltre riconosciuta un'indennità per ripetibili (art. 159 cpv. 1 e 2 OG; <ref-ruling> consid. 7).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso di diritto amministrativo è respinto.
2. Nella misura in cui è ammissibile, il ricorso di diritto pubblico è respinto.
3. La tassa di giustizia complessiva di fr. 5'000.-- è posta, in solido, a carico dei ricorrenti, che, pure in solido, rifonderanno al Comune di Bissone un'indennità unica di fr. 2'500.-- a titolo di ripetibili della sede federale.
4. Comunicazione ai patrocinatori dei ricorrenti e del Municipio di Bissone, al Dipartimento del territorio, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino, nonché all'Ufficio federale dell'ambiente, delle foreste e del paesaggio.