Sachverhalt: A. Die SBB AG ist Eigentümerin der Parzelle Nr. 5677 in Gossau, welche im Spickel zweier sich keilförmig verzweigender Bahnlinien, etwa 300 m westlich des Bahnhofs, liegt; sie ist im Wesentlichen mit Infrastrukturanlagen für den Bahnbetrieb überbaut. Am 18. Dezember 2012 erteilte die Baukommission Gossau der Salt Mobile SA (im Folgenden: Salt) die Baubewilligung für die Errichtung einer Mobilfunkanlage auf dem Grundstück Nr. 5677 unter verschiedenen Auflagen und Bedingungen und wies die zahlreichen Einsprachen ab. Am 13. März 2014 wies das Baudepartement des Kantons St. Gallen den von A._ und 63 Mitbeteiligten erhobenen Rekurs im Sinne der Erwägungen ab, soweit es darauf eintrat. Am 27. Oktober 2015 wies das Verwaltungsgericht des Kantons St. Gallen die von A._ und 63 Mitbeteiligten gegen diesen Rekursentscheid erhobene Beschwerde ab und versah die Baubewilligung im Sinne der Erwägungen mit einer zusätzlichen Auflage. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen A._ und 63 Mitbeteiligte, das Urteil des Verwaltungsgerichts aufzuheben und die Baubewilligung zu verweigern oder die Sache eventuell ans Verwaltungsgericht zu neuem Entscheid zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen sie, ihrer Beschwerde aufschiebende Wirkung zu erteilen. C. Am 21. Januar 2016 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zu. D. Das Verwaltungsgericht und das Baudepartement beantragen, die Beschwerde abzuweisen. Die Salt beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. E. Das Bundesamt für Umwelt (BAFU) reicht eine Vernehmlassung ein, ohne einen Antrag zu stellen. F. A._ und die 63 Mitbeteiligten halten an ihrer Beschwerde fest.