Sachverhalt:
A. Am 11. Dezember 2003 bewilligte die Baukommission Lindau der TDC Switzerland AG die Erstellung einer Mobilfunk-Antennenanlage auf dem Flachdach des Gebäudes Rietstrasse 4 in Tagelswangen (Kat.-Nr. 967), Gemeinde Lindau.
B. Dagegen führte die A._ zusammen mit 151 Rekurrenten am 19. Januar 2004 Rekurs an die Baurekurskommission III. Diese wies den Rekurs am 23. März 2005 ab, soweit sie darauf eintrat.
C. Gegen den Rekursentscheid erhob die A._ zusammen mit 141 weiteren Beschwerdeführern Beschwerde an das Verwaltungsgericht des Kantons Zürich. Am 8. Februar 2006 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat.
D. Gegen den verwaltungsgerichtlichen Entscheid haben die A._ und die übrigen Beschwerdeführer am 16. März 2006 Verwaltungsgerichtsbeschwerde und staatsrechtliche Beschwerde ans Bundesgericht erhoben.
Sie beantragen die Aufhebung der Entscheide des Verwaltungsgerichts, der Baurekurskommission und der Baukommission Lindau; eventualiter sei die Sache zur weiteren Abklärung des Sachverhalts an die Baukommission, subeventualiter an die Baurekurskommission und subsubeventualiter an das Verwaltungsgericht zurückzuweisen. Für den Fall, dass die Baubewilligung erteilt werden müsse, verlangen die Beschwerdeführer eventualiter die Anordnung zusätzlicher Auflagen betreffend Kontrollmessungen und Informationspflichten der Antennenbetreiberin.
In verfahrensmässiger Hinsicht beantragen die Beschwerdeführer, ihnen sei nach Zustellung der Akten der Vorinstanzen die Möglichkeit der Beschwerdeergänzung einzuräumen. Zudem sei den Beschwerden aufschiebende Wirkung zu gewähren und das Verfahren zu sistieren, bis nachgewiesenermassen alle durch die Mobilfunkantennen verursachten Immissionen an allen relevanten Punkten unabhängig von jeglicher Einflussnahme der Beschwerdegegnerin einwandfrei bestimmt seien, eine übergeordnete, zumindest regionale Planung bezüglich Koordination der Mobilfunkantennen vorliege und eine formelle Umweltverträglichkeitsprüfung durchgeführt worden sei; alsdann sei eine neue öffentliche Auflage des Baugesuches durchzuführen. Sodann ersuchen sie um die Durchführung eines Augenscheins, an dem den Beschwerdeführern und den von ihnen allenfalls beigezogenen Fachleuten genügend Zeit für mündliche Stellungnahmen einzuräumen sei. Überdies sei ein zweiter Schriftenwechsel und eine öffentliche mündliche Verhandlung durchzuführen.
E. Mit Schreiben vom 16. März 2006 reichte der Rechtsvertreter der Beschwerdeführer eine "Beschwerdeergänzung" ein. Am 18. April 2006 reichten drei Beschwerdeführer im Namen aller "Rekurrenten gegen Mobilfunkantenne" zusätzliche Unterlagen ein.
F. Die TDC Switzerland AG und das Verwaltungsgericht beantragen, die Beschwerden seien abzuweisen, soweit darauf einzutreten sei. Die Baukommission Lindau hat sich nicht vernehmen lassen.
G. Das Bundesamt für Umwelt (BAFU) bestätigt in seiner Vernehmlassung grundsätzlich die Richtigkeit der Entscheide der Vorinstanzen und deren Begründungen. Es kritisiert allerdings das Fehlen detaillierter Angaben für die mechanischen und elektrischen Neigungswinkel im Zusatzblatt 2 des Standortdatenblatts und hält eine Überschreitung des Anlagegrenzwerts für möglich, falls das Dach des Standortgebäudes tatsächlich nicht völlig kompakt sein sollte (OMEN Nr. 2) und falls auf der nicht überbauten Parzelle Nr. 971 (Roosenacher) ein Ort mit empfindlicher Nutzung in mindestens 10 m Höhe über den Boden errichtet werden könnte. Den Beteiligten wurde Gelegenheit gegeben, hierzu Stellung zu nehmen.
H. Mit Schreiben vom 4. September 2006 reichte die Beschwerdegegnerin ein neues Standortdatenblatt ein, in dem die Winkelbereiche gemäss den Anforderungen des BAFU verbindlich in einen elektrischen und mechanischen Neigungswinkel aufgeteilt sind. Ausserdem reichte sie Fotos des Standortgebäudes und ein Exemplar des Zonenplans der Gemeinde Lindau ein. Das Schreiben und dessen Beilagen wurden den Beschwerdeführern zugestellt.
I. Am 5. Oktober 2006 replizierten die Beschwerdeführer. Die Replik wurde der Beschwerdegegnerin zur Kenntnisnahme zugestellt.
J. Mit Verfügung vom 5. Mai 2006 erteilte der Präsident der I. öffentlichrechtlichen Abteilung den Beschwerden insoweit die aufschiebende Wirkung, als die Inbetriebnahme und Sendetätigkeit der Antennen während des bundesgerichtlichen Verfahrens zu unterbleiben habe. Der Antrag auf Sistierung des Verfahrens wurde abgewiesen.

Das Bundesgericht zieht in Erwägung:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid, der sich in erster Linie auf die Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) und damit auf Bundesverwaltungsrecht stützt. Dagegen steht die Verwaltungsgerichtsbeschwerde ans Bundesgericht grundsätzlich offen (Art. 97 ff. OG), soweit die Verletzung von Bundesrecht geltend gemacht wird. Dazu gehört auch die Rüge, Verfahrensgarantien der Bundesverfassung bzw. der EMRK seien im verwaltungsgerichtlichen Verfahren verletzt worden.
1.1 Die Rüge, kantonales Recht sei willkürlich angewendet worden, kann dagegen im Verfahren der Verwaltungsgerichtsbeschwerde nur dann mitbeurteilt werden, wenn ein hinreichend enger Sachzusammenhang zwischen ihr und der zu beurteilenden Frage des Bundesverwaltungsrechts besteht (<ref-ruling> E. 2b S. 277; <ref-ruling> E. 1b S. 75; je mit Hinweisen). Dies ist zu bejahen, soweit die Beschwerdeführer geltend machen, die Mobilfunkanlage sei aufgrund ihrer Immissionen in der Gewerbezone G3 nicht zonenkonform, weil es sich um einen äusserst stark störenden Betrieb handle.
1.2 Die Beschwerdeführer sind grösstenteils Bewohner oder Benützer von Liegenschaften in der Nähe des Baugrundstücks und sind als solche zur Verwaltungsgerichtsbeschwerde legitimiert (Art. 103 lit. a OG). Es kann daher - wie schon im verwaltungsgerichtlichen Verfahren - offen bleiben, ob auch die rund 10 Beschwerdeführer, die ihren Wohnsitz bzw. Sitz nicht in Tagelswangen haben, ebenfalls zur Beschwerde berechtigt sind.
1.3 Auf die rechtzeitig erhobene Verwaltungsgerichtsbeschwerde ist daher grundsätzlich einzutreten.
Allerdings ist die am 17. März 2006 bei der Post aufgegebene Beschwerdeergänzung verspätet, da die Beschwerdefrist, wie der Rechtsvertreter der Beschwerdeführer selbst berechnet hat (Beschwerdeschrift Ziff. II.1 S. 9), am 16. März 2006 abgelaufen war. Es ist auch kein Grund ersichtlich, den Beschwerdeführern eine zusätzliche Frist zur Beschwerdeergänzung einzuräumen. Die Beschwerdeergänzung ist daher im Folgenden nicht zu berücksichtigen.
Gleiches gilt für die unaufgefordert und ohne Zusammenhang mit den Vernehmlassungen der Vorinstanz oder der Beschwerdegegnerin eingereichten Unterlagen vom 18. April 2006.
2. Soweit die Beschwerdeführer die Verletzung von selbständigem kantonalen Bau- und Planungsrecht rügen, das keinen engen Zusammenhang mit dem Bundesumweltrecht aufweist, steht nur die staatsrechtliche Beschwerde zur Verfügung. Allerdings kann auf die in diesem Verfahren zu beurteilenden Rügen, wie im Folgenden darzulegen sein wird, nicht eingetreten werden.
2.1 Die Beschwerdeführer rügen zum einen, die kantonalen Instanzen hätten nicht geprüft, ob eine gültige Zustimmung des Grundeigentümers zum Bauvorhaben vorliege. Sie legen aber nicht dar, welche Norm des kantonalen Baurechts inwiefern in verfassungswidriger Weise angewandt worden sei. Ist auf diese Rüge somit mangels rechtsgenügender Begründung nicht einzutreten (Art. 90 Abs. 1 lit. b OG), kann offen bleiben, ob die Beschwerdeführer überhaupt zur Erhebung dieser Rüge legitimiert wären (vgl. dazu Entscheid 1A.160/2004 vom 10. März 2005 E. 1.3.2).
2.2 Auch soweit die Beschwerdeführer pauschal rügen, die kantonalen Instanzen hätten nicht von Amtes wegen geprüft, ob sämtliche kantonalen und kommunalen Pläne und Bestimmungen beachtet und alle nach kantonalem Recht erforderlichen Unterlagen öffentlich aufgelegt worden seien, fehlt es an der nach Art. 90 Abs. 1 lit. b OG erforderlichen substantiierten Begründung einer Verfassungsverletzung.
2.3 Die Beschwerdeführer rügen überdies, die Höhe des Mobilfunkmasts bzw. der damit verbundenen Container verstosse gegen die in der Bau- und Zonenordnung für die Gewerbezone erlassene Höhenbeschränkung. Sie setzen sich aber mit der Begründung des Verwaltungsgerichts, wonach die Mobilfunkanlage kein selbständiges Gebäude sei, das an die Vorschriften betreffend Gebäude- und Firsthöhe gebunden wäre, nicht auseinander, und legen nicht dar, inwiefern diese Erwägungen willkürlich sind.
2.4 Nach dem Gesagten ist auf die staatsrechtliche Beschwerde nicht einzutreten. Im Folgenden sind daher nur die in der Verwaltungsgerichtsbeschwerde zu beurteilenden Rügen zu prüfen.
3. Die Beschwerdeführer rügen eine Verletzung von 6 Ziff. 1 EMRK, weil das Verwaltungsgericht keinen zweiten Schriftenwechsel und keine öffentliche Verhandlung durchgeführt habe, obwohl dies ausdrücklich beantragt worden sei.
3.1 Das Verwaltungsgericht nahm an, es liege keine "civil-rights"-Streitigkeit i.S.v. Art. 6 Ziff. 1 EMRK vor, weil die Beschwerdeführer nicht geltend gemacht hätten, dass der Anlagegrenzwert bei den von ihnen bewohnten bzw. benutzten Liegenschaften überschritten sei. Zwar werde der Anlagegrenzwert am OMEN Nr. 9 an der Rietstrasse 6 mit 4.95 V/m nur knapp unterschritten; diese Berechnung sei aber von den Beschwerdeführern nicht konkret beanstandet worden; diese hätten vielmehr die Berechnungen insgesamt als willkürlich bezeichnet und vermutet, dass die Grenzwerte an anderen OMEN überschritten seien (angefochtener Entscheid E. 4.3 S. 15).
3.2 Das Bundesgericht bejaht das Vorliegen von "civil rights" i.S.v. Art. 6 Ziff. 1 EMRK im Bau- und Planungsrecht, wenn ein Nachbar die Verletzung von Normen geltend macht, die auch seinem Schutz dienen (vgl. <ref-ruling> E. 2c S. 45 f.). In <ref-ruling> E. 2a/bb S. 61 f. hat das Bundesgericht entschieden, dass die Immissions- und Anlagegrenzwerte der NISV nachbarschützend seien und Art. 6 Ziff. 1 EMRK deshalb Anwendung findet, wenn ein Beschwerdeführer geltend macht, diese Grenzwerte seien auf seinem Grundstück überschritten. Werden dagegen die vorsorglichen Grenzwerte der NISV eingehalten, besteht in aller Regel keine hinreichende Wahrscheinlichkeit ernsthafter Auswirkungen für die Gesundheit oder die körperliche Integrität der Beschwerdeführer, die unabhängig von der Ausgestaltung des nationalen Rechts zur Anwendung von Art. 6 EMRK führt (<ref-ruling> E. 2a/cc S. 62 mit Hinweisen zur Rechtsprechung des EGMR).
3.3 Aufgrund dieser publizierten Praxis müssen Beschwerdeführer, die eine Verletzung von Art. 6 Ziff. 1 EMRK im kantonalen Verfahren rügen, darlegen, dass sie im kantonalen Gerichtsverfahren die Nichteinhaltung der Anlage- oder Immissionsgrenzwerte der NISV auf ihnen gehörenden oder von ihnen gemieteten Grundstücken geltend gemacht haben. Es ist - auch im Verfahren der Verwaltungsgerichtsbeschwerde - nicht Aufgabe des Bundesgerichts, die vorinstanzlichen Akten auf derartige Rügen hin zu durchsuchen bzw. anhand der Adressen der Beschwerdeführer oder anderer Anhaltspunkt herauszufinden, welche Orte mit empfindlicher Nutzung (OMEN), auf denen die Anlagegrenzwerte möglicherweise überschritten sein könnten, sich auf den Liegenschaften bzw. in den Wohnungen der Beschwerdeführer befinden.
Im vorliegenden Fall berufen sich die anwaltlich vertretenen Beschwerdeführer auf Art. 6 EMRK mit dem pauschalen Hinweis, dass sie die Verletzung von "Privatrechten" wie Eigentum, Gesundheit, körperliche Unversehrtheit, usw. gerügt hätten; dies genügt nach dem oben Gesagten nicht.
4. Zu prüfen ist jedoch, ob der Anspruch auf rechtliches Gehör gemäss Art. 29 Abs. 2 BV verletzt wurde, weil den Beschwerdeführern keine Möglichkeit eingeräumt wurde, sich zur Vernehmlassung der Beschwerdegegnerin zu äussern.
4.1 Im verwaltungsgerichtlichen Verfahren reichte die private Beschwerdegegnerin am 8. Juni 2005 eine umfangreiche Vernehmlassung sowie einen Bericht der Forschungsstiftung Mobilkommunikation vom 3. Februar 2004 zur TNO-Studie ein. Die Vernehmlassung wurde den Beschwerdeführern am 21. Juni 2005 zur Kenntnisnahme zugestellt; ein zweiter Schriftenwechsel wurde nicht angeordnet. Am 16. Dezember 2005 beantragte der Rechtsvertreter der Beschwerdeführer, sich zu den Stellungnahmen und Akten der Gegenpartei äussern zu können. Ausserdem ersuchte er um Einsichtnahme in sämtliche Akten bzw. in all jene Akten, die ihm nicht bereits in einem früheren Verfahrensstadium zugestellt worden waren. Mit Präsidialverfügung vom 3. Januar 2006 wurde das Akteneinsichtsbegehren gutgeheissen; dagegen wurde kein zweiter Schriftenwechsel angeordnet, weil die Beschwerdeantwort der privaten Beschwerdegegnerin weder neue rechtliche Gesichtspunkte noch neue tatsächliche Behauptungen enthalte.
4.2 Unter der Geltung von Art. 4 aBV ergab sich aus dem Anspruch auf rechtliches Gehör nach ständiger Rechtsprechung keine generelle Pflicht zur Einräumung eines Replikrechts. Eine Vernehmlassung musste den Verfahrensbeteiligten nur dann zur Stellungnahme zugestellt werden, wenn darin neue und erhebliche Gesichtspunkte geltend gemacht wurden, zu denen die Beteiligten sich noch nicht hatten äussern können (<ref-ruling> E. 3 S. 3; <ref-ruling> E. 4b S. 314; <ref-ruling> E. 1 S. 323). Ungebetene Stellungnahmen wurden grundsätzlich aus dem Recht gewiesen.
4.3 Nach ständiger Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte (EGMR) umfasst das Recht auf ein faires Verfahren gemäss Art. 6 Ziff. 1 EMRK das Recht der Parteien, von jedem Aktenstück und jeder dem Gericht eingereichten Stellungnahme Kenntnis zu nehmen und sich dazu äussern zu können, sofern sie dies für erforderlich halten (Urteil Niederöst-Huber c. Schweiz vom 18. Februar 1997, Rec.CourEDH 1997-I S. 101 ff. § 24, mit Hinweis auf die Urteile Lobo Machado c. Portugal und Vermeulen c. Belgique vom 20. Februar 1996, Rec.CourEDH 1996-I S. 206 § 31 und S. 234 § 33).
Unerheblich ist nach der Rechtsprechung des EGMR, ob eine Eingabe neue Tatsachen oder Argumente enthält und ob sie das Gericht tatsächlich zu beeinflussen vermag: Es sei Sache der Parteien zu beurteilen, ob ein Dokument einen Kommentar erfordere; das Vertrauen der Rechtsuchenden in die Justiz gründe u.a. auf der Gewissheit, sich zu jedem Aktenstück äussern zu können (Urteile Niederöst-Huber, a.a.O. §§ 27 und 29; vgl. aus jüngster Zeit die Urteile Ressegatti c. Schweiz vom 13. Juli 2006 §§ 30-33 und Spang c. Schweiz vom 11. Oktober 2005 §§ 32 f., Letzteres publ. in Plädoyer 2005/6 S. 82).
Wird dem Beschwerdeführer keine Möglichkeit eingeräumt, zu den Bemerkungen des Beschwerdegegners Stellung zu nehmen, ist nach der Rechtsprechung des EGMR auch das Prinzip der Waffengleichheit verletzt, das Bestandteil des Rechts auf ein faires Gerichtsverfahren ist (Urteil Ressegatti, a.a.O., § 33).
4.4 Bei der Totalrevision der Bundesverfassung wurden die von der bundesgerichtlichen Rechtsprechung zu Art. 4 aBV konkretisierten Teilaspekte des Verbots der formellen Rechtsverweigerung in einem Verfassungsartikel, dem heutigen Art. 29 BV, zusammengefasst. In diesen Artikel wurden auch die allgemeinen Verfahrensgarantien integriert, die sich aus verschiedenen internationalen Übereinkommen ergeben. Dazu gehört namentlich der in den Art. 6 EMRK und 14 UNO Pakt II verankerte Grundsatz des "fair trial" bzw. des "procès équitable" und die diesbezügliche Rechtsprechung (Botschaft des Bundesrats über eine neue Bundesverfassung vom 20. November 1996, BBl 1997 I 181 zu Art. 25 E-BV).
4.5 Nach Inkrafttreten der neuen Bundesverfassung führte das Bundesgericht seine Rechtsprechung zum rechtlichen Gehör grundsätzlich fort. Betont wurde jedoch, dass der Anspruch auf rechtliches Gehör ein wichtiger und deshalb eigens aufgeführter Teilaspekt des allgemeinen Grundsatzes des fairen Verfahrens von Art. 29 Abs. 1 BV bzw. Art. 6 Ziff. 1 EMRK ist (<ref-ruling> E. 4.1 S. 88).
Aus dieser Erkenntnis wurde in verschiedenen nicht veröffentlichten Entscheiden gefolgert, dass der Rechtsprechung des EGMR zum "fair trial" auch bei der Auslegung von Art. 29 Abs. 2 BV Rechnung getragen werden muss.
So wurde im Urteil 1P.730/2001 vom 31. Januar 2002 (E. 2.1) unter Berufung auf die Strassburger Rechtsprechung angenommen, dass der Angeschuldigte, der ein Ausstandsgesuch stellt, Anspruch auf Zustellung und auf Stellungnahme zu den Vernehmlassungen der Staatsanwaltschaft und des abgelehnten Richters habe, unabhängig davon, ob diese Eingaben neue und erhebliche Gesichtspunkte enthalten. Es genüge, wenn der Antrag auf Abweisung des Ausstandsgesuchs in den Vernehmlassungen gestellt und begründet werde (vgl. auch Urteile 1P.245/2006 vom 12. Juli 2006 E. 2.1 und 1P.337/2006 vom 4. September 2002 E. 2.2).
Im nicht veröffentlichten Urteil 1P.798/2005 vom 8. Februar 2006 (E. 2), das ein Baubeschwerdeverfahren betrifft, bejahte das Bundesgericht gestützt auf Art. 29 Abs. 2 BV einen verfassungsmässigen Anspruch des Beschwerdeführers auf Stellungnahme zu einer substanziellen Beschwerdeantwort der Vorinstanz und der privaten Beschwerdegegner. Auch in diesem Entscheid prüfte das Bundesgericht nicht, ob die Vernehmlassungen der Vorinstanz und der Beschwerdegegner neue und erhebliche Gesichtspunkte enthielten, sondern liess es genügen, dass darin Ausführungen zum Sachverhalt und zur Rechtslage gemacht wurden, die nicht von vornherein ungeeignet waren, den Verfahrensausgang zu beeinflussen.
4.6 Dieser Rechtsprechung liegt die Überlegung zugrunde, dass die Grundsätze des "fair trial" gemäss Art. 6 Ziff. 1 EMRK in Art. 29 Abs. 1 BV als allgemeine Verfahrensgrundsätze übernommen worden sind und deshalb für alle gerichtlichen Verfahren gelten.
Die meisten Gerichtsverfahren unterliegen heute bereits den Garantien von Art. 6 Ziff. 1 EMRK, die nicht nur auf zivil- und strafrechtliche Verfahren im engeren Sinne, sondern auch auf zahlreiche Streitigkeiten im Bereich des Sozialversicherungs- und des Verwaltungsrechts anwendbar sind (vgl. z.B. Mark E. Villiger, Probleme der Anwendung von Art. 6 Abs. 1 EMRK auf verwaltungs- und sozialgerichtliche Verfahren, AJP 4/1995 S. 163-171; Ruth Herzog, Art. 6 EMRK und kantonale Verwaltungsrechtspflege, Bern 1995; Andreas Kley-Struller, Art. 6 EMRK als Rechtsschutzgarantie gegen die öffentliche Gewalt: Die aktuelle Praxis der Konventionsorgane zur Anwendung des Art. 6 EMRK in der Verwaltungsrechtspflege: Analysen und Perspektiven, Zürich 1993). In allen diesen Verfahren sind die Gerichte nach der Rechtsprechung des EGMR verpflichtet, jede ihnen eingereichte Stellungnahme den Beteiligten zur Kenntnis zu bringen und diesen Gelegenheit zu geben, dazu Stellung zu nehmen. Es ist kein Grund ersichtlich, für die verbleibenden, nicht in den Schutzbereich von Art. 6 Ziff. 1 EMRK fallenden Gerichtsverfahren das rechtliche Gehör restriktiver zu fassen.
4.7 Im vorliegenden Fall hatte die private Beschwerdegegnerin im verwaltungsgerichtlichen Verfahren eine umfangreiche Vernehmlassung mit Ausführungen zur Sach- und Rechtslage eingereicht. Nachdem die Beschwerdeführer eine Stellungnahme hiezu für notwendig erachtet und einen entsprechenden Antrag bei Gericht gestellt hatten, hätte ihnen dieses Recht gewährt werden müssen.
Stattdessen entschied das Verwaltungsgericht mit Präsidialverfügung vom 3. Januar 2006, dass kein zweiter Schriftenwechsel angeordnet werde. Damit wurde nicht nur die Durchführung eines zweiten Schriftenwechsels im engeren Sinne (mit Replik und Duplik) abgelehnt, sondern auch der Antrag der Beschwerdeführer vom 16. Dezember 2005 auf Stellungnahme zur Vernehmlassung der Gegenpartei und damit um Gewährung des rechtlichen Gehörs abgewiesen.
4.8 Dieser Antrag war allerdings sehr spät, fast sechs Monate nach Zustellung der Vernehmlassung, gestellt worden. Nach der neueren bundesgerichtlichen Rechtsprechung muss der Beschwerdeführer, welcher eine Stellungnahme zu einer ihm zur Kenntnisnahme zugestellten Vernehmlassung für erforderlich hält, diese grundsätzlich unverzüglich einreichen oder beantragen; andernfalls ist davon auszugehen, dass er auf eine Stellungnahme verzichtet (<ref-ruling> E. 3.3.3 und 3.3.4 S. 47; <ref-ruling> E. 2.2 S. 99).
Im vorliegenden Fall war den Beschwerdeführern allerdings die Beschwerdeantwort mit dem Vermerk zugestellt worden, es sei kein 2. Schriftenwechsel angeordnet worden. Insofern mussten sie davon ausgehen, dass eine ungebetene Stellungnahme ihrerseits unerwünscht sei (vgl. Urteil 1P.798/2005 vom 8. Februar 2006, E. 2.3).
Im Übrigen ist das Verwaltungsgericht auf die Eingabe der Beschwerdeführer vom 16. Dezember 2005 eingetreten und hat das darin mitenthaltene Gesuch um Akteneinsicht gutgeheissen. Das Verwaltungsgericht wollte mit der nachträglichen Aktenzustellung die von den Beschwerdeführern gerügte Verletzung des Akteneinsichtsrechts im Rekursverfahren heilen (vgl. angefochtener Entscheid E. 4.2 S. 14). Damit war das Verfahren im Dezember 2005 noch nicht entscheidungsreif: Das Verwaltungsgericht musste abwarten, bis die Akteneinsicht erfolgt war und musste auch mit einer Stellungnahme der Beschwerdeführer zu den neu eingesehenen Unterlagen rechnen.
Unter diesen Umständen kann weder ein Verzicht auf das Recht zur Stellungnahme noch eine Verwirkung desselben angenommen werden.
4.9 Die beschriebene Verletzung des rechtlichen Gehörs kann im bundesgerichtlichen Verfahren nicht geheilt werden, wenn - wie im vorliegenden Fall - nicht nur Rechtsfragen streitig sind, sondern auch Sachverhaltsrügen erhoben werden, die das Bundesgericht nicht mit freier Kognition beurteilen kann (vgl. Art. 105 Abs. 2 OG).
5. Die Verwaltungsgerichtsbeschwerde ist daher gutzuheissen und die Sache an das Verwaltungsgericht zurückzuweisen.
Unter den gegebenen Umständen erscheint es angemessen, auf die Erhebung von Gerichtskosten zu verzichten. Dagegen hat die obsiegende Partei Anspruch auf eine Parteientschädigung; diese ist von der privaten Beschwerdegegnerin zu entrichten, auch wenn ihr die Verletzung des rechtlichen Gehörs nicht angelastet werden kann (Art. 159 OG).

Demnach erkennt das Bundesgericht:
1. Auf die staatsrechtliche Beschwerde wird nicht eingetreten.
2. In Gutheissung der Verwaltungsgerichtsbeschwerde wird der Entscheid des Verwaltungsgerichts des Kantons Zürich, 1. Abteilung, 1. Kammer, vom 8. Februar 2006 aufgehoben. Die Sache wird zu neuer Beurteilung an das Verwaltungsgericht zurückgewiesen.
3. Es werden keine Kosten erhoben.
4. Die TDC Switzerland AG hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien, der Baukommission der Gemeinde Lindau, der Baurekurskommission III und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, sowie dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 11. Januar 2007
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: