Sachverhalt:
A.
Am 22. Dezember 2016 stellte die Baugesellschaft G._ das Gesuch um Erstellung eines Kinos (acht Säle mit 1'390 Sitzplätzen) mit Nebennutzungen (Shopbereich, Restaurant, Bar, Eventraum, Minigolfanlage) und mit einer Einstellhalle sowie einer Fussgänger-Passerelle ins Einkaufs- und Gewerbecenter G._ (nachfolgend: EGC) auf der Parzelle 13182 in Chur. Die Passerelle soll von der Parzelle 13182 über die Bahngeleise der Rhätischen Bahn ins EGC (Parzelle 8979) führen. Das geplante Restaurant soll 250 m2, die Bar 200 m2 und der Mehrzweckraum 500 m2 Geschossfläche umfassen. Die gesamte Geschossfläche des geplanten Gebäudes beträgt 13'367 m2. Vorgesehen sind 154 Parkplätze. Zulasten der Parzelle 8979 und zugunsten der Parzelle 13182, welche beide im Eigentum der Baugesellschaft G._ stehen, wurde ein Mitbenützungsrecht an 35 Besucherparkplätzen im bestehenden Parkhaus des EGC vereinbart. Die übrigen 119 Parkplätze sind im Neubau des Kinocenters G._ geplant.
Das Baugesuch lag vom 6. Januar bis 26. Januar 2017 auf. Dagegen erhoben unter anderem A._, B._, C._ D._, E._ und F._ am 25. Januar 2017 gemeinsam Einsprache.
Mit Zirkulationsbeschluss vom 1. Juni 2017 wies die Stadt Chur die Einsprache ab, soweit sie darauf eintrat, und bewilligte das Baugesuch unter Bedingungen und Auflagen.
Dagegen reichten die obgenannten Personen am 3. Juli 2017 Beschwerde beim Verwaltungsgericht des Kantons Graubünden ein.
Mit Urteil vom 10. April 2018 hiess das Verwaltungsgericht die Beschwerde teilweise gut und ergänzte den Baubescheid durch die klarstellende Auflage, dass 35 Parkplätze im EGC von den Besuchern des Kinocenters G._ mitbenutzt werden dürfen und ihnen während der Stosszeiten des Kinocenters zur Verfügung stehen müssen. Im Übrigen wies es die Beschwerde ab.
B.
A._, B._, C._ D._, E._ und F._ führen mit Eingabe vom 13. Juni 2018 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht mit dem Hauptantrag auf Aufhebung des angefochtenen Urteils des Verwaltungsgerichts vom 10. April 2018.
Mit Verfügung vom 10. Juli 2018 wies der Präsident der I. öffentlich-rechtlichen Abteilung das Gesuch der Beschwerdeführer um aufschiebende Wirkung ab.
Das Verwaltungsgericht, die Stadt Chur und die Baugesellschaft G._ (Beschwerdegegnerin) beantragen in ihren Vernehmlassungen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne.
Das Bundesamt für Umwelt BAFU hat eine Stellungnahme eingereicht, ohne Anträge zu stellen. Im Ergebnis erachtet es das angefochtene Urteil als konform mit dem Umweltrecht des Bundes.
Die Beschwerdeführer und die Beschwerdegegnerin halten in weiteren Eingaben an ihrem Standpunkt und an ihren Anträgen fest.

Erwägungen:
1.
1.1. Dem angefochtenen Urteil der Vorinstanz liegt eine baurechtliche Streitigkeit und damit eine öffentlich-rechtliche Angelegenheit zugrunde. Das Bundesgerichtsgesetz enthält auf dem Gebiet des Raumplanungs- und Baurechts keinen Ausschlussgrund von der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a und Art. 83 BGG). Die Beschwerdeführer sind Nachbarn im baurechtlichen Sinn und hatten im vorinstanzlichen Verfahren Parteistellung. Sie sind durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung. Sie sind damit zur Beschwerdeführung berechtigt (<ref-law>).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten können Rechtsverletzungen im Sinne von <ref-law> gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Hinsichtlich der Verletzung von Grundrechten gilt eine qualifizierte Rügepflicht (<ref-law>; vgl. <ref-ruling> E. 1.6 S. 281 f.).
1.3. Gemäss <ref-law> dürfen neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Abs. 1). Neue Begehren sind unzulässig (Abs. 2). Nicht unter das Novenverbot fallen neue rechtliche Vorbringen (vgl. hierzu Urteil des Bundesgerichts 1C_582/2013 vom 25. September 2013 E. 1.4).
Die Beschwerdeführer rügen im bundesgerichtlichen Verfahren erstmals, die kantonalen und kommunalen Behörden hätten Fehler bei der Bestimmung des Umfangs der Umweltverträglichkeitsprüfung (UVP) gemacht. Es sei von einem engen räumlichen und funktionalen Zusammenhang zwischen dem geplanten Projekt (Kino mit Nebennutzungen) und dem EGC auszugehen, weshalb eine Gesamtanlage im Rechtssinne (vgl. <ref-law> [SR 814.01]) vorliege, die insgesamt der UVP unterstehe.
Dies stellt entgegen der Auffassung der Beschwerdegegnerin eine Rechts- und nicht eine Tatfrage dar. Das Vorbringen erweist sich als zulässig (vgl. nachfolgend E. 4 ff.).
2.
Die Beschwerdeführer erachten <ref-law> als verletzt. Die Vorinstanz sei ihrer Begründungspflicht nur ungenügend nachgekommen und habe sich nicht mit ihren Rügen zum befürchteten überdurchschnittlichen Verkehrsaufkommen und zum Verkehrskonzept auseinandergesetzt.
Die Vorinstanz hat sich im angefochtenen Urteil (E. 5b) unter Verweis auf den Beurteilungsbericht des kantonalen Amts für Natur und Umwelt (ANU/GR) vom 20. März 2017 zwar knapp, aber doch hinreichend mit den diesbezüglichen Rügen der Beschwerdeführer befasst. Die Vorinstanz hat die bestehende Verkehrserschliessung gewürdigt und begründet, warum sich diese ihres Erachtens aus tatsächlicher und rechtlicher Hinsicht als genügend erweist.
Die Rüge der Verletzung der Begründungspflicht erweist sich als nicht stichhaltig (vgl. auch <ref-ruling>E. 9.2 S. 65).
3.
3.1. Gemäss <ref-law> werden Einwirkungen sowohl einzeln als auch gesamthaft und nach ihrem Zusammenwirken beurteilt.
Bevor eine Behörde über die Planung, Errichtung oder Änderung von Anlagen entscheidet, prüft sie möglichst frühzeitig die Umweltverträglichkeit (<ref-law>). Wer eine Anlage, die der Umweltverträglichkeitsprüfung untersteht, planen, errichten oder ändern will, muss der zuständigen Behörde einen Umweltverträglichkeitsbericht unterbreiten. Dieser bildet die Grundlage der Umweltverträglichkeitsprüfung (<ref-law>).
Gemäss Art. 2 Abs. 1 lit. a der Verordnung vom 19. Oktober 1988 über die Umweltverträglichkeitsprüfung (UVPV; SR 814.011) unterliegen Änderungen bestehender Anlagen, die im Anhang aufgeführt sind, der Prüfung, wenn die Änderung wesentliche Umbauten, Erweiterungen oder Betriebsänderungen betrifft. Bei der Prüfung wird nach <ref-law> festgestellt, ob das Projekt den Vorschriften über den Schutz der Umwelt entspricht. Dazu gehören das USG und die Vorschriften, die den Natur- und Heimatschutz, den Landschaftsschutz, den Gewässerschutz, die Walderhaltung, die Jagd, die Fischerei und die Gentechnik betreffen.
Gemäss Anhang zur UVPV unterstehen namentlich Parkhäuser und -plätze für mehr als 500 Motorwagen (Anhang UVPV Ziffer 11.4) sowie Einkaufszentren und Fachmärkte mit einer Verkaufsfläche von mehr als 7'500 m2 (Anhang UVPV Ziffer 80.5) der UVP-Pflicht. Gleiches gilt für Vergnügungsparks mit einer Fläche von mehr als 75'000 m2 oder für eine Kapazität von mehr als 4'000 Besuchern pro Tag (Anhang UVPV Ziffer 60.6).
Nach <ref-law> werden Luftverunreinigungen, Lärm, Erschütterungen und Strahlen durch Massnahmen bei der Quelle begrenzt (Emissionsbegrenzungen; Abs. 1). Unabhängig von der bestehenden Umweltbelastung sind Emissionen im Rahmen der Vorsorge so weit zu begrenzen, als dies technisch und betrieblich möglich und wirtschaftlich tragbar ist (Abs. 2). Die Emissionsbegrenzungen werden verschärft, wenn feststeht oder zu erwarten ist, dass die Einwirkungen unter Berücksichtigung der bestehenden Umweltbelastung schädlich oder lästig werden (Abs. 3).
3.2. Gemäss Art. 2 Abs. 4 lit. a der Luftreinhalte-Verordnung vom 16. Dezember 1985 (LRV; SR 814.318.142.1) gelten als neue Anlagen auch Anlagen, die umgebaut, erweitert oder instand gestellt werden, wenn dadurch höhere oder andere Emissionen zu erwarten sind.
3.3. Nach Art. 8 der Lärmschutz-Verordnung vom 15. Dezember 1986 (LSV; SR 814.41) müssen bei einer wesentlichen Änderung einer ortsfesten Anlage die Lärmemissionen der gesamten Anlage mindestens so weit begrenzt werden, dass die Immissionsgrenzwerte nicht überschritten werden (Abs. 2). Als wesentliche Änderungen ortsfester Anlagen gelten Umbauten, Erweiterungen und vom Inhaber der Anlage verursachte Änderungen des Betriebs, wenn zu erwarten ist, dass die Anlage selbst oder die Mehrbeanspruchung bestehender Verkehrsanlagen wahrnehmbar stärkere Lärmimmissionen erzeugt (vgl. Abs. 3).
4.
4.1. Die Beschwerdeführer bringen, wie dargelegt (E. 1.3), vor, es bestehe ein enger räumlicher und funktionaler Zusammenhang zwischen dem geplanten Projekt und dem EGC, weshalb eine Gesamtanlage im Rechtssinne vorliege, die insgesamt der UVP unterstehe. Sie berufen sich dabei insbesondere auf die bundesgerichtliche Rechtsprechung, konkret auf <ref-ruling>.
Die Beschwerdeführer führen aus, die Verfasserin des Umweltberichts vom 22. Dezember 2016, die Tuffli & Partner AG, sei zu Unrecht davon ausgegangen, es bestehe keine UVP-Pflicht. Das ANU/GR bejahe zwar eine solche Pflicht, habe es jedoch versäumt, den Umweltbericht ergänzen zu lassen. Hinzu komme, dass das ANU/GR fälschlicherweise geschlossen habe, es bestehe nur ein geringer funktionaler Zusammenhang zwischen den Parkierungsanlagen des geplanten Kinocenters und des EGC, weshalb die neu geplante Parkierungsanlage mit 119 Parkplätzen als Einzelanlage beurteilt werden könne. Diese Auffassung widerspreche der bundesgerichtlichen Rechtsprechung. Ein funktionaler Zusammenhang sei aufgrund der Eigentümer- und Betreiberverhältnisse, der gemeinsamen Nutzung der Parkplätze, der Verbindung mit einer Passerelle und der Erschliessung eindeutig zu bejahen. Zusammenfassend hätten die Emissionsbegrenzungen für die gesamte Anlage in der UVP geprüft und im Bewilligungsentscheid festgesetzt werden müssen. Konkret kritisieren die Beschwerdeführer die Bereiche Luftreinhaltung und Lärmschutz.
4.2. Im Umweltbericht der Tuffli & Partner AG vom 22. Dezember 2016, auf welchen die Beschwerdeführer in ihrer Beschwerde verweisen, wird festgehalten, gemäss <ref-law> würden wesentliche Änderungen bestehender UVP-pflichtiger Anlagen der UVP unterliegen. Das bestehende EGC weise eine Verkaufsfläche inkl. Restaurants von rund 20'000 m2 sowie eine Parkierungsanlage mit 681 Parkfeldern auf, womit die massgeblichen Schwellenwerte überschritten seien (Anhang UVPV Ziffer 80.5: Einkaufszentren mit einer Verkaufsfläche von mehr als 7'500 m2; Anhang UVPV Ziffer 11.4: Parkhäuser und -plätze für mehr als 500 Motorwagen; vgl. hierzu auch E. 3.1 hiervor). Es sei deshalb 2007 im Rahmen des Baubewilligungsverfahrens eine Umweltverträglichkeitsprüfung durchgeführt worden (Umweltverträglichkeitsbericht der Tuffli & Partner AG vom 21. September 2007). Der geplante Neubau des Kinos überschreite demgegenüber mit 154 Parkplätzen weder den Schwellenwert für Parkhäuser und -parkplätze noch für einen anderen Anlagetyp gemäss Anhang UVPV. Durch die geplante Passerelle zwischen dem Kinocenter und dem EGC bestehe zwar eine räumliche Verbindung. Funktional sei jedoch aufgrund der Doppelnutzung von 35 Parkplätzen nur von einem geringen Zusammenhang auszugehen. Die Nutzung bzw. die Anzahl erzeugter Fahrten werde durch den Betrieb des Kinocenters erhöht, womit es sich um eine Änderung einer bestehenden UVP-pflichtigen Anlage handle. Allerdings sei bei der Parkierungsanlage des EGC bloss eine Erhöhung des Verkehrsaufkommens um rund 4 % zu erwarten, weshalb es sich um keine wesentliche Änderung der bestehenden UVP-pflichtigen Anlage handle. Der vorliegende Bericht werde deshalb als Umweltbericht (und nicht als Umweltverträglichkeitsbericht) bezeichnet und dem Baugesuch beigelegt (vgl. zum Ganzen Umweltbericht der Tuffli & Partner AG vom 22. Dezember 2016, S. 3 f.).
4.3. Im Beurteilungsbericht des ANU/GR vom 20. März 2017 wird demgegenüber davon ausgegangen, aufgrund der Erhöhung der Fahrten (Kundenverkehr) durch das geplante Kinocenter liege eine wesentliche Änderung einer bestehenden UVP-pflichtigen Anlage, d.h. des EGC vor. Zudem handle es sich je nach Besucheraufkommen um eine Anlage, die für eine Kapazität von 4'000 Besuchern pro Tag ausgerichtet sein könne. Daher unterliege das Kinocenter (auch) gestützt auf Anhang UVPV Ziffer 60.6 der UVP (vgl. Beurteilungsbericht des ANU/GR vom 20. März 2017, S. 4).
Der von der Tuffli & Partner AG erstellte Umweltbericht vom 22. Dezember 2016 zeige die zum heutigen Zeitpunkt absehbaren Konflikte mit den in <ref-law> aufgeführten Umweltbereichen vollständig auf. Betreffend die Lufthygiene (Betriebsphase) wird im Beurteilungsbericht festgehalten, es sei geplant, die Wärme für Raumheizung und Warmwasser für das Kinocenter aus dem bestehenden Blockheizkraftwerk des EGC zu beziehen, was begrüsst werde. Zwischen den Parkierungsanlagen des Kinocenters (119 Parkplätze) und des EGC (681 Parkplätze) bestehe nur ein geringer (funktionaler) Zusammenhang, da nur 35 der 681 bestehenden Parkplätze auch dem Kinocenter dienten (Doppelnutzung). Die Parkierungsanlage des Kinocenters könne daher als Einzelanlage beurteilt werden (vgl. Beurteilungsbericht des ANU/GR vom 20. März 2017, S. 5).
4.4. Im Baubescheid der Stadt Chur vom 1. Juni 2017 wird in Übereinstimmung mit der Auffassung des ANU/GR die UVP-Pflicht bejaht. Die Frage des notwendigen Umfangs der UVP wird indes nicht thematisiert und es wird nicht diskutiert, ob ein räumlicher und funktionaler Zusammenhang zwischen dem geplanten Projekt und dem EGC bestehe (vgl. Baubescheid der Stadt Chur vom 1. Juni 2017, S. 2 und S. 7).
4.5. Im angefochtenen Urteil der Vorinstanz vom 10. April 2018 bildet der Aspekt der UVP-Pflicht kein Thema.
4.6. Die Stadt Chur hebt in ihrer Stellungnahme im bundesgerichtlichen Verfahren vom 14. August 2018 hervor, sowohl die Baubehörde als auch das ANU/GR gingen jedenfalls aufgrund der Erhöhung der Fahrten von einer wesentlichen Änderung einer bestehenden UVP-pflichtigen Anlage und damit von einer UVP-Pflicht aus (Vernehmlassung der Stadt Chur vom 14. August 2018, S. 5).
4.7. Die Beschwerdegegnerin bestreitet in ihrer Vernehmlassung im bundesgerichtlichen Verfahren vom 23. August 2018 die UVP-Pflicht nicht ausdrücklich. Sie stellt sich indes auf den Standpunkt, ein funktionaler Zusammenhang zwischen dem geplanten Kino mit Nebennutzungen und dem EGC sei zu verneinen. Sie beruft sich gleich den Beschwerdeführern auf <ref-ruling>. Die Beschwerdegegnerin betont, die gemeinsame Nutzung von 35 Parkplätzen in der Tiefgarage des EGC, die Passerelle zwischen den beiden Gebäuden und die gemeinsame Heizung - der Kinoneubau werde für dessen Beheizung an das im EGC befindliche Blockheizkraftwerk angeschlossen -, reichten nicht aus, um einen engen funktionalen Zusammenhang zu bejahen. Es würden zwar Synergien genutzt, es liege aber keine betriebliche Einheit vor, was auch durch die "nicht gänzlich identische" Trägerschaft zwischen dem Kino und dem EGC verdeutlicht werde. Das ANU/GR habe das Vorliegen einer Gesamtanlage zu Recht verneint (Vernehmlassung der Beschwerdegegnerin vom 23. August 2018, S. 5 ff.).
4.8. Das BAFU führt in seiner Stellungnahme im bundesgerichtlichen Verfahren vom 1. Oktober 2018 aus, das in <ref-law> normierte Prinzip der ganzheitlichen Betrachtungsweise verlange nach der bundesgerichtlichen Rechtsprechung (<ref-ruling>) insbesondere für den Bereich der Emissionsbegrenzung eine gesamtheitliche Beurteilung aller Anlagen, die aufgrund ihres räumlichen und funktionalen Zusammenhangs als Gesamtanlage erscheinen würden. Aufgrund der Passerellen-Verbindung bestehe ein räumlicher Zusammenhang. Bezüglich des funktionalen Zusammenhangs sei zu berücksichtigen, dass die beiden Grundstücke (zumindest teilweise) im Eigentum der Beschwerdegegnerin stünden. Aufgrund der Doppelnutzung von 35 Parkplätzen bestehe ein gewisser Berührungspunkt; diese Parkplätze seien für die Kinobesucher nur zu Fuss über die geplante Passerelle erreichbar. Diese beiden Aspekte (Eigentümerverhältnisse und gemeinsame Nutzung der Parkplätze) genügten jedoch nicht, um einen funktionalen Zusammenhang zu begründen. Es liege keine Gesamtanlage vor. Eine gemeinsame Beurteilung der Einzelanlagen habe nicht durchgeführt werden müssen (Vernehmlassung des BAFU vom 1. Oktober 2018, S. 2 f.).
Mangels eines hinreichenden funktionalen Zusammenhangs sei der Bau des geplanten Kinocenters auch nicht als Änderung oder Erweiterung des bereits bestehenden EGC im Sinne von Art. 2 Abs. 4 lit. a LRV zu betrachten (Vernehmlassung des BAFU vom 1. Oktober 2018, S. 4).
Schliesslich führe die Doppelnutzung der 35 Parkplätze nicht dazu, dass die Anlage selbst oder die Mehrbeanspruchung bestehender Verkehrsanlagen wahrnehmbar stärkere Lärmimmissionen erzeugten. Es liege keine wesentliche Änderung des bestehenden Einkaufszentrums im Sinne von <ref-law> vor (Vernehmlassung des BAFU vom 1. Oktober 2018, S. 6).
5.
5.1. Im zu beurteilenden Fall ist die UVP-Pflicht als solche seitens der Parteien und beteiligten kommunalen und kantonalen Behörden unbestritten. Strittig ist hingegen der gebotene Umfang der erforderlichen UVP, gehen doch die Beschwerdegegnerin, die Baubewilligungsbehörde und das BAFU im Unterschied zu den Beschwerdeführern davon aus, es liege keine Gesamtanlage im Sinne von <ref-law> vor (vgl. hierzu E. 4.3 - 4.8 hiervor).
5.2. Die Parteien und das BAFU berufen sich auf <ref-ruling>. In diesem Entscheid befasste sich das Bundesgericht mit der Frage, wann eine Mehrzahl von Einzelanlagen eine betriebliche Einheit und damit eine Gesamtanlage im Rechtssinne bilden, die insgesamt der UVP unterliegt. Es kam zum Schluss, Voraussetzung sei neben der räumlichen Nähe ein enger funktionaler Zusammenhang, d.h. ein Zusammenwirken über das behördlich Gebotene hinaus. Dies setze bei verschiedenen Eigentümern/Betreibern eine gewisse gemeinsame Organisation oder Planung voraus (vgl. Regeste zu <ref-ruling>).
Im Einzelnen erwog das Bundesgericht, was folgt: <ref-law> und das darin zugrunde liegende Prinzip der ganzheitlichen Betrachtungsweise verlangen - insbesondere für den Bereich der Emissionsbegrenzung - eine gesamthafte Beurteilung aller Anlagen, die aufgrund ihres räumlichen, zeitlichen und funktionalen Zusammenhangs als Gesamtanlage erscheinen. Daraus wird gefolgert, dass die UVP-Pflicht sich auf alle Teile erstrecken muss, die zusammen eine Gesamtanlage in diesem Sinne bilden. Speziell für den Bereich der Luftreinhaltung bestimmt Art. 2 Abs. 4 LRV, dass als neue Anlagen auch Anlagen gelten, die umgebaut, erweitert oder instand gestellt werden, wenn dadurch höhere oder andere Emissionen zu erwarten sind. Ist das zu bewilligende Projekt in diesem Sinne als Änderung oder Erweiterung einer bereits bestehenden Anlage zu qualifizieren, so müssen die erforderlichen Emissionsbegrenzungen für die gesamte Anlage in der UVP geprüft und im Bewilligungsentscheid festgesetzt werden, d.h. nicht nur hinsichtlich der neuen, sondern auch der bestehenden Teile (vgl. <ref-ruling> E. 3.1 S. 25 f.).
Eine betriebliche Einheit verschiedener Anlagen (teile) setzt praxisgemäss neben der räumlichen Nähe einen engen funktionalen Zusammenhang voraus: Die einzelnen Teile müssen sich derart ergänzen, dass sie gemeinsam eine betriebliche Einheit bilden oder bilden könnten. Der Einheitscharakter von verschiedenen Vorhaben, die von unterschiedlichen Bauherrschaften errichtet werden, kann gemäss Urteil des Bundesgerichts 1A.110/2006 vom 19. April 2007 E. 2.7.1 und 2.7.2 (in: URP 2005 S. 228 ff.) nicht leichthin angenommen werden, da das USG keine planerische, sondern nur eine projektbezogene UVP kennt. Gemeinsame umwelt- und planungsrechtliche Vorgaben der Behörden (z.B. Pflicht zur Beteiligung an einem Parkleitsystem) genügen nicht. Sofern es sich nicht um die gleiche Bauherrschaft handelt, muss zumindest eine gemeinsame Organisation oder Zwecksetzung der verschiedenen Bauherrschaften existieren (vgl. <ref-ruling> E. 3.2 S. 26 f.).
Näher zu betrachten ist die Rechtsprechung zu Art. 2 Abs. 4 LRV (<ref-ruling> E. 2.1.2 S. 107 f.; Urteile des Bundesgerichts 1A.239/2006 vom 10. Juli 2007 und 1A.293/2005 vom 10. Juli 2006 [in: URP 2006 S. 894]). Gemeinsam ist den Fällen, dass es sich um verschiedene Bauherrschaften und selbstständig betreibbare Einrichtungen handelte (Fachmärkte bzw. Freizeiteinrichtungen), die aber nach aussen als Einheit auftraten (Einkaufszentrum bzw. Freizeitpark) oder über gewisse Gemeinschaftsanlagen verfügten (gemeinsame Parkanlagen im Fall 1A.293/2005). Dies setzt ein Minimum an gemeinsamer Organisation und Planung voraus (vgl. <ref-ruling> E. 3.4 S. 27 ff.).
Zusammenfassend kann festgehalten werden, dass eine Gesamtanlage in der Regel nur angenommen werden kann, wenn zwei (oder mehrere) Einzelanlagen zumindest in Teilbereichen zusammenwirken, und zwar über das durch behördliche Auflagen Gebotene hinaus. Gehören die Einzelanlagen demselben Eigentümer/Betreiber oder besteht eine gemeinsame Organisation oder Planung, so kann ein funktionaler Zusammenhang eher angenommen werden (vgl. <ref-ruling> E. 3.5 S. 29).
Im von den Streitbeteiligten als Referenzentscheid angerufenen Leiturteil bejahte das Bundesgericht trotz fehlender gemeinsamer Verwaltung einen massgebenden funktionalen Zusammenhang (zwischen dem Limmat-Parkhaus und dem Shoppi Tivoli). Es wies insbesondere darauf hin, dass die Verkaufsflächen des Limmatparks durch eine Fussgängerverbindung (Passerelle) mit dem Tivoli verbunden werden, dass auf der Internetseite für sämtliche Geschäfte geworben werde, dass das Limmat-Parkhaus zu einem grossen Teil den Eigentümern des Shoppi Tivoli gehöre und dass ein Verbund bei den Parkierungsflächen bestehe (vgl. <ref-ruling> E. 6 S. 31 ff.).
5.3. Im zu beurteilenden Fall kann die räumliche Nähe zwischen dem geplanten Kinocenter und dem EGC nicht zweifelhaft sein. Umstritten ist, ob auch ein enger funktionaler Zusammenhang vorliegt.
Das Bundesgericht hat in <ref-ruling> klargestellt, dass für den Umfang der UVP-Pflicht entscheidend ist, ob von einer Gesamtanlage ausgegangen werden kann, mithin, ob zwei (oder mehrere) Einzelanlagen zumindest in Teilbereichen zusammenwirken, und zwar über das durch behördliche Auflagen Gebotene hinaus (vgl. Daniela Thurnherr, in: Fachhandbuch Öffentliches Baurecht, 2016, Rz. 7.169). Während bei unterschiedlichen Bauherrschaften zumindest eine gemeinsame Organisation oder Zwecksetzung existieren muss, sind bei gleichen Eigentümern oder Betreibern geringere Anforderungen an die Bejahung eines funktionalen Zusammenhangs zu stellen.
Die Beschwerdegegnerin ist Eigentümerin beider Anlagen bzw. Grundstücke. Identisch ist bei den beiden Projekten auch die Bauherrschaft; diese ist an der einfachen Gesellschaft der Beschwerdegegnerin beteiligt. Die Passerellen-Verbindung ermöglicht es den Kunden, zu Fuss zwischen den beiden Anlagen zu zirkulieren und so die verschiedenen, sich ergänzenden Angebote (Ladengeschäfte, Kinos und Restaurants) zu nutzen, was im objektiven Interesse der Beschwerdegegnerin liegt. Die beiden Einzelanlagen wirken auch sonst über das behördlich Gebotene hinaus zusammen. So ist die gemeinsame Nutzung bzw. Doppelnutzung von Parkplätzen nicht von den Behörden vorgeschrieben worden, sondern der Beschwerdegegnerin wurde hierfür auf ihr Ersuchen hin gestützt auf Art. 7 der Parkplatzverordnung vom 5. Oktober 2006 der Stadt Chur (RB 613) eine Ausnahmebewilligung erteilt (vgl. hierzu Baubescheid der Stadt Chur vom 1. Juni 2017, S. 14, und angefochtenes Urteil vom 10. April 2018, S. 20). Zudem soll das Kinocenter die Wärme für Raumheizung und Warmwasser aus dem bestehenden Blockheizkraftwerk des EGC beziehen, sodass auch insoweit Synergien genutzt werden.
Unter diesen Umständen ist ein massgebender funktionaler Zusammenhang zwischen dem geplanten Kinoneubau und dem EGC zu bejahen. Dass im Unterschied zum Sachverhalt in <ref-ruling> (noch) keine gemeinsame Werbung betrieben wird, ist nicht entscheidend, da das Kinocenter noch nicht erstellt ist. Angesichts des gemeinsamen Namens "G._" (Einkaufs- und Gewerbecenter G._ respektive Kinocenter G._) wäre ein einheitlicher Internet- bzw. Werbeauftritt jedenfalls ohne Weiteres möglich. Zudem wird für die Kundschaft mit dem gemeinsamen Namen der Eindruck eines einzigen, zusammengehörenden Einkaufs- und Freizeitzentrums erweckt.
5.4. Die Rüge der Beschwerdeführer erweist sich damit als begründet. Entgegen den Ausführungen im Umweltbericht der Tuffli & Partner AG vom 22. Dezember 2016 (E. 4.2 hiervor) ist funktional nicht nur von einem geringen Zusammenhang auszugehen, und entgegen der Auffassung des ANU/GR (E. 4.3 hiervor) und des BAFU (E. 4.8 hiervor) durfte die Parkierungsanlage des Kinocenters daher nicht als Einzelanlage beurteilt werden respektive war eine gemeinsame Beurteilung der Einzelanlagen als Gesamtanlage geboten.
5.5. Soweit das BAFU im Übrigen eine wesentliche Änderung des bestehenden Einkaufszentrums im Sinne von <ref-law> verneint (vgl. E. 4.8 hiervor am Ende), steht diese Einschätzung nicht mit den vom BAFU selbst erarbeiteten Grundsätzen für die Beurteilung der UVP-Pflicht von Änderungen bestehender UVP-pflichtiger Anlagen in Einklang. Im Regelfall gelten nämlich bei Parkplätzen für mehr als 500 Motorwagen (Anhang UVPV Ziffer 11.4) Anlagenerweiterungen im Umfang von mehr als 100 Parkplätzen (bzw. mehr als 20 % des Schwellenwerts für neue Anlagen) als wesentlich und damit als UVP-pflichtig (vgl. BAFU, UVP-Handbuch, Richtlinie des Bundes für die Umweltverträglichkeitsprüfung [<ref-law> und <ref-law>], 2009, S. 17).
6.
6.1. Die Beschwerdeführer rügen, wie dargelegt (E. 4.1 hiervor), Fehler bei der Durchführung der UVP, da die Tuffli & Partner AG im Umweltbericht vom 22. Dezember 2016 die UVP-Pflicht zu Unrecht verneint und das ANU/GR es in der Folge versäumt habe, den Umweltbericht ergänzen zu lassen. Im Rahmen der Rechtsanwendung von Amtes wegen gemäss <ref-law> (vgl. E. 1.2 hiervor) ist auf den verfahrensrechtlichen Aspekt der UVP-Pflicht näher einzugehen.
6.2. Gemäss <ref-law> steht gesamtschweizerisch tätigen Umweltschutzorganisationen, die rein ideelle Zwecke verfolgen, gegen Verfügungen der kantonalen Behörden oder der Bundesbehörden über die Planung, Errichtung oder Änderung von Anlagen, für die eine UVP nach <ref-law> erforderlich ist, das Beschwerderecht zu (Verbandsbeschwerde). Nach <ref-law> eröffnet die Behörde den Organisationen ihre Verfügung nach <ref-law> durch schriftliche Mitteilung oder durch Veröffentlichung im Bundesblatt oder im kantonalen Publikationsorgan (Abs. 1). Sieht das Bundesrecht oder das kantonale Recht ein Einspracheverfahren vor, so sind auch die Gesuche nach Abs. 1 zu veröffentlichen (Abs. 2).
6.3. Die Anforderungen an den Text der Ausschreibung sind bei einem UVP-pflichtigen Vorhaben streng. Aus der Anknüpfung des Verbandsbeschwerderechts an die UVP-Pflichtigkeit eines Vorhabens und der Obliegenheit der Organisationen, sich bereits am Einspracheverfahren zu beteiligen, folgt, dass anhand der Publikation erkennbar sein muss, ob es sich um ein UVP-pflichtiges Vorhaben handelt und ob damit das Verbandsbeschwerderecht offensteht. Ein Hinweis auf benachbarte Anlagen, die möglicherweise in einem funktionalen Zusammenhang mit der geplanten Anlage stehen und bei der Ermittlung der Schwellenwerte zu berücksichtigen sind, ist etwa dann erforderlich, wenn eine neue Parkierungsanlage direkt mit einer bestehenden verbunden wird (vgl. Alain Griffel / Heribert Rausch, Kommentar zum Umweltschutgesetz, Ergänzungsband zur 2. Auflage, 2011, N. 7 zu <ref-law>; vgl. auch Alain Griffel, Umweltrecht in a nutshell, 2015, S. 45).
6.4. Gleiches ergibt sich auch aus dem kantonalem Recht. Gemäss Art. 45 der Raumplanungsverordnung vom 24. Mai 2005 des Kantons Graubünden (KRVO/GR; BR 801.110), auf welchen die Stadt Chur in ihrem Baubescheid ausdrücklich verweist (Baubescheid vom 1. Juni 2017, S. 5), legt die kommunale Baubehörde nach Abschluss der vorläufigen Prüfung das Baugesuch während 20 Tagen in der Gemeinde öffentlich auf. Erfordert das Bauvorhaben eine UVP, wird gleichzeitig der Umweltverträglichkeitsbericht (UVB) aufgelegt (Abs. 1). Einsprachen sind während der Auflagefrist bei der Gemeinde einzureichen (Abs. 4).
6.5. Bei der öffentlichen Auflage des Baugesuchs vom 6. bis 26. Januar 2017 (vgl. Sachverhalt lit. A. hiervor) wurde soweit aktenkundig nicht auf die UVP-Pflicht hingewiesen, obwohl die Stadt Chur als Baubewilligungsbehörde in Übereinstimmung mit der Einschätzung des ANU/GR die UVP-Pflicht später bejaht hat (vgl. Beurteilungsbericht des ANU/GR vom 20. März 2017 [E. 4.3. hiervor], Baubescheid der Stadt Chur vom 1. Juni 2017 [E. 4.4 hiervor] und Vernehmlassung der Stadt Chur vom 14. August 2018 [E. 4.6 hiervor]). Teil der Auflageakten bildete vielmehr der dem Baugesuch beigelegte Umweltbericht der Tuffli & Partner AG vom 22. Dezember 2016, in welchem die UVP-Pflicht ausdrücklich verneint wurde (vgl. E. 4.2 hiervor).
Damit wurden die dargestellten verfahrensrechtlichen Vorgaben (vgl. E. 6.3 und E. 6.4 hiervor) nicht eingehalten. Als Folge davon wurde den Umweltschutzorganisation zu Unrecht die Möglichkeit verwehrt, von ihrem Verbandsbeschwerderecht Gebrauch zu machen und Einsprache zu erheben.
7.
Bei unterbliebener oder unvollständiger bzw. fehlerhafter UVP ist im Verfahren der Anfechtung einer (noch nicht rechtskräftigen) Bewilligung vom Grundsatz der Aufhebung der Bewilligung auszugehen, sofern aufgrund der vorliegenden Informationen die Bewilligungsfähigkeit nicht erstellt ist (Thurnherr, a.a.O., Rz. 7.213).
Im zu beurteilenden Fall liegt nach dem Gesagten eine Gesamtanlage im Sinne von <ref-law> vor, die gesamthaft der UVP untersteht. Eine gemeinsame Beurteilung der Einzelanlagen als Gesamtanlage war geboten; die Prüfung ist mithin inhaltlich mangelhaft durchgeführt worden (vgl. E. 5 hiervor). Des Weiteren wurden Verfahrensvorschriften verletzt (vgl. E. 6 hiervor). Die Baubewilligung wurde folglich auf der Grundlage einer unvollständigen bzw. fehlerhaften UVP erteilt, weshalb die Bewilligung aufzuheben ist, da die Bewilligungsfähigkeit nicht erstellt ist.
Bei diesem Ergebnis erübrigt sich ein Eingehen auf die weiteren Rügen der Beschwerdeführer (insbesondere angeblich fehlende rechtliche Sicherstellung der Passerelle, angeblich fehlende Sicherheitsbeurteilung und angeblich fehlendes Mobilitätskonzept).
8.
Die Beschwerde ist gutzuheissen. Das angefochtene Urteil und die Baubewilligung sind aufzuheben. Die Sache ist an die Stadt Chur zurückzuweisen (vgl. insoweit auch Urteil 1C_289/2013 vom 28. Oktober 2013 E. 5). Will die Beschwerdegegnerin an ihrem Bauvorhaben festhalten, ist der Umweltbericht der Tuffli & Partner AG vom 22. Dezember 2016 zu ergänzen und es ist eine Gesamtbeurteilung im Sinne von <ref-law> vorzunehmen. Der Umweltverträglichkeitsbericht ist alsdann öffentlich aufzulegen.
Die Kosten des bundesgerichtlichen Verfahrens sind der unterliegenden Beschwerdegegnerin aufzuerlegen (<ref-law>). Diese hat den obsiegenden Beschwerdeführern eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Die Sache ist zur Neuregelung der Kosten- und Entschädigungsfolgen für das kantonale Verfahren an die Vorinstanz zurückzuweisen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Verwaltungsgerichts des Kantons Graubünden vom 10. April 2018 und die Baubewilligung der Stadt Chur vom 1. Juni 2017 werden aufgehoben. Die Sache wird im Sinne der Erwägungen an die Stadt Chur zurückgewiesen.
2.
Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 4'000.-- zu entschädigen.
4.
Die Angelegenheit wird zur Neuregelung der Kosten- und Entschädigungsfolgen für das kantonale Verfahren an die Vorinstanz zurückgewiesen.
5.
Dieses Urteil wird den Parteien, der Stadt Chur, dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, und dem Bundesamt für Umwelt BAFU schriftlich mitgeteilt.
Lausanne, 3. Juli 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Gerber