Sachverhalt: A. Am 20. Dezember 2004 erteilte der Stadtrat Baden der TDC Switzerland AG die Baubewilligung für die Errichtung einer GSM/UMTS-Mobilfunkanlage auf dem Hochhaus Linde an der Mellingerstrasse 22 (Parzelle Nr. 1679) in Baden und wies die gegen das Bauvorhaben erhobenen Einsprachen ab. Zuvor hatte die kantonale Koordinationsstelle Baugesuche dem Bauvorhaben am 14. September 2004 unter Auflagen zugestimmt. B. Dagegen erhoben Eheleute X._ und weitere Einsprecher Verwaltungsbeschwerde an den Regierungsrat des Kantons Aargau. Dieser wies die Beschwerde am 24. August 2005 ab. C. Gegen den regierungsrätlichen Entscheid gelangten die Eheleute X._ und weitere Einsprecher am 30. September 2005 an das Verwaltungsgericht des Kantons Aargau. Dieses wies die Beschwerde am 20. Dezember 2006 ab. D. Dagegen haben Eheleute X._ und die weiteren im Rubrum genannten natürlichen und juristischen Personen am 12. Februar 2007 Verwaltungsgerichtsbeschwerde und staatsrechtliche Beschwerde ans Bundesgericht erhoben. Sie beantragen, das angefochtene Urteil sei aufzuheben und die Sache sei zur Neubeurteilung an die Erstinstanz zurückzuweisen. Eventualiter sei die Baubewilligung unter einschränkenden Bedingungen zu erteilen, insbesondere mit der Auflage, dass die Mobilfunkanlage weniger prominent in Erscheinung trete. E. Die TDC Switzerland AG (im Folgenden: die Beschwerdegegnerin) und die Stadt Baden schliessen auf Abweisung der Beschwerden. Der Regierungsrat und das Verwaltungsgericht haben auf eine Vernehmlassung verzichtet. Am 25. April 2007 reichte die Beschwerdegegnerin einen animierten fotografischen Bericht ein, um aufzuzeigen, dass die projektierte und bewilligte Mobilfunkantenne optisch bescheiden in Erscheinung treten werde. F. Das Bundesamt für Kultur vertritt in seiner Vernehmlassung die Auffassung, die geplante Antennenanlage stelle keine erhebliche Beeinträchtigung des im Bundesinventar über Ortsbilder von nationaler Bedeutung (ISOS) aufgenommenen Ortsbilds von Baden/Ennetbaden dar. Das Bundesamt für Umwelt hat auf eine Vernehmlassung verzichtet. G. Mit Verfügung vom 15. März 2007 wurde den Beschwerden aufschiebende Wirkung erteilt.