Sachverhalt: A. Am 28. November 1999 beschlossen die Stimmbürgerinnen und Stimmbürger der Einwohnergemeinde Bern eine Änderung des Nutzungszonen- und Bauklassenplans Brünnen, der Überbauungsordnung (ÜO) Brünnen sowie der zugehörigen Überbauungsvorschriften (ÜV). Ziel der Vorlage war, im Bereich der Autobahnausfahrt Brünnen nebst der Wohnnutzung die Erstellung eines Freizeit- und Einkaufszentrums zu ermöglichen. Die Planänderung wurde am 5. Juli 2000 vom Amt für Gemeinden und Raumordnung des Kantons Bern genehmigt und ist unangefochten geblieben. Umweltrechtliche Grundlage der Planung bildete die erste Stufe einer Umweltverträglichkeitsprüfung (UVP) im Sinne von Art. 9 des Bundesgesetzes vom 7. Oktober 1983 über den Umweltschutz (Umweltschutzgesetz, USG; SR 814.01) bzw. Ziff. 80.5 des Anhangs zur Verordnung vom 19. Oktober 1988 über die Umweltverträglichkeitsprüfung (UVPV; SR 814.011). Die neuen Vorschriften zum Nutzungszonen- und Bauklassenplan Brünnen lassen in der Dienstleistungs- und Gewerbezone (DG) Verkaufs- und Freizeitnutzungen von maximal 42'000 m2 Bruttogeschossfläche zu, wobei der Anteil der Verkaufsnutzungen auf 23'500 m2 beschränkt ist; davon dürfen höchstens 2'500 m2 auf kundenintensive Verbrauchermärkte mit Gütern des täglichen und wöchentlichen Bedarfs entfallen. Im Weiteren ist auf einem Teil der Dienstleistungs- und Gewerbezone ein Wohnanteil von 30 % zu realisieren. Zum Schutz der Wohnbevölkerung in Bern-West beschlossen die Stimmbürgerinnen und Stimmbürger am 28. November 1999 zusammen mit der Änderung der Planung Brünnen einen Brutto-Rahmenkredit von Fr. 12,9 Mio. für die Realisierung flankierender Verkehrs- und Lärmschutzmassnahmen. Das Konzept umfasst die Projekte Lärmschutz entlang der Bottigenstrasse in Bümpliz, neuer Fuss- und Radweg entlang dem Moosweg, Lärmschutzbauwerk und -fenster entlang der Murtenstrasse im Bereich Gäbelbach und die Umfahrung Niederbottigen. Der Standort Brünnen gilt gemäss dem vom Regierungsrat des Kantons Bern am 27. Februar 2002 erlassenen kantonalen Richtplan als kantonaler Entwicklungsschwerpunkt. Im regionalen Richtplan vom 20. Juni 2003 (Teil 1: Einkaufs- und Freizeitstandorte, Regionsstruktur und Mobilität) ist Brünnen als Standort für verkehrsintensive Vorhaben von regionaler Bedeutung bezeichnet. B. Am 28. Februar 2002 reichte die Neue Brünnen AG beim Bauinspektorat der Stadt Bern ein Baugesuch für das Projekt "WESTside Brünnen" in der Dienstleistungs- und Gewerbezone Brünnen ein. Das Vorhaben umfasst ein Freizeit- und Einkaufszentrum mit Gastgewerbebetrieben, einem Freizeitbad, einem Media Convention Center mit 10 Kinosälen, einer Tankstelle, einem Fachmarkt, einem Garten Center, einem Hotel und einer Seniorenresidenz. Es sollen eine Erschliessungsstrasse und 1'400 Autoabstellplätze erstellt werden. Das Vorhaben soll eine breite Bevölkerungsschicht ansprechen und eine erlebnisorientierte Kombination von Freizeit- und Konsumaktivitäten mit einem regionalen Einzugsgebiet bieten. Die Neue Brünnen AG hat sich im Rahmen von Infrastrukturverträgen zu Beiträgen an verschiedene Infrastrukturmassnahmen verpflichtet (Erstellung der S-Bahnstation Brünnen, Autobahnüberdeckung, Investitionen in öffentliche Verkehrsmittel "BernMobil", flankierende Massnahmen der Stadt Bern). Mit dem Baugesuch hat die Neue Brünnen AG einen in ihrem Auftrag erstellten Umweltverträglichkeitsbericht (UVB) vom Dezember 2002 eingereicht. Die kantonale Koordinationsstelle für Umweltschutz führte unter Beizug der betroffenen Fachstellen eine UVP 2. Stufe durch und erstellte am 25. Februar 2003 eine Gesamtbeurteilung zu Handen des Regierungsstatthalters I von Bern als zuständiger Leit- bzw. Baubewilligungsbehörde. Die Koordinationsstelle für Umweltschutz kommt zum Schluss, mit den in der UVP-Gesamtbeurteilung aufgeführten Auflagen sei das Bauvorhaben umweltverträglich. Mit Gesamtbauentscheid vom 12. August 2003 erteilte der Regierungsstatthalter I von Bern die nachgesuchte Bewilligung unter zahlreichen Auflagen und Bedingungen. C. Gegen den Entscheid des Regierungsstatthalters erhoben insgesamt 28 Einsprechende Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern (BVE). Am 3. Dezember 2003 reichte die Neue Brünnen AG eine Projektänderung betreffend die Zufahrt Nord und die Parkplatzsituation Nord mitsamt einem diesbezüglichen Lärmgutachten ein. Gegen die Projektänderung erhoben mehrere Beschwerdeführende Einsprache bei der BVE. Nach Durchführung weiterer Instruktionsmassnahmen wies die BVE die Beschwerden, soweit sie darauf eintrat, mit Entscheid vom 15. April 2004 weitgehend ab, bewilligte die im Beschwerdeverfahren von der Baugesuchstellerin eingereichte Projektänderung und erteilte dem Vorhaben WESTside erneut die Gesamtbaubewilligung unter zahlreichen Auflagen und Bedingungen. D. Gegen diesen Entscheid der BVE erhoben Kurt Gilgen und zahlreiche Mitbeteiligte beim Verwaltungsgericht des Kantons Bern Verwaltungsgerichtsbeschwerde. Die Beschwerdeführer machten im Wesentlichen geltend, das Vorhaben sei nicht umweltverträglich, weil viele entscheidende Faktoren zu ungenau, nicht belegt und spekulativ seien oder auf falschen und unklaren Angaben beruhten. Die Umweltauswirkungen erwiesen sich als unabsehbar, weshalb das Projekt den rechtlichen Voraussetzungen nicht genüge und nicht bewilligt werden könne. Mit Urteil vom 20. Dezember 2004 hiess das Verwaltungsgericht die Beschwerde teilweise gut und änderte einige Nebenbestimmungen des Entscheids der BVE. Im Übrigen wies es die Beschwerde ab, soweit es darauf eintreten konnte. E. Gegen das Urteil des Verwaltungsgerichts vom 20. Dezember 2004 haben Kurt Gilgen und 12 Mitbeteiligte am 31. Januar 2005 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht. Sie beantragen die Aufhebung des Urteils des Verwaltungsgerichts und verlangen überdies, die Entscheide des Regierungsstatthalters und der BVE seien als hinfällig zu bezeichnen und dem Vorhaben sei der Bauabschlag zu erteilen. F. Die Neue Brünnen AG, die Stadt Bern und das Verwaltungsgericht beantragen, die Verwaltungsgerichtsbeschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die BVE verzichtet auf eine Vernehmlassung. Der Regierungsstatthalter von Bern schliesst auf Abweisung der Beschwerde. Das Bundesamt für Umwelt, Wald und Landschaft (BUWAL) hat sich am 14. März 2005 zur vorliegenden Angelegenheit vernehmen lassen. Es gelangt zum Schluss, das Projekt sei umweltverträglich und somit bundesrechtskonform. Die Parteien erhielten Gelegenheit, sich zur Stellungnahme des BUWAL zu äussern; zudem wurden die Beschwerdeführer zur Replik eingeladen. G. Mit Verfügung vom 22. Februar 2005 hat der Präsident der I. öffentlichrechtlichen Abteilung das Gesuch der Beschwerdeführer um aufschiebende Wirkung abgewiesen.