Sachverhalt: A. Die Seilbahn Rickenbach-Rotenfluh AG reichte ein Plangenehmigungs- und Konzessionsgesuch für den Bau einer Umlaufkabinenbahn Rickenbach-Rätigs-Rotenfluh sowie ein Baugesuch für eine Parkierungsanlage bei der neuen Talstation ein. Beide Vorhaben wurden im Amtsblatt des Kantons Schwyz vom 6. Juli 2012 publiziert und öffentlich aufgelegt. Gegen die projektierte Parkierungsanlage (nicht aber gegen die Luftseilbahn) erhoben A._, B._ und C._ fristgerecht Einsprache. Geplant ist ein zweigeschossiges Parkhaus auf Parzelle KTN 2052, mit einer Länge von knapp 100 m (entlang der Rickenbachstrasse) und einer Höhe (an der Südfassade) von rund 7 m; im Norden soll das Parkhaus in den Hang gebaut werden. Im Erdgeschoss sind 64 und im Obergeschoss 62 Abstellplätze vorgesehen. In den Wintermonaten soll die Decke über dem Obergeschoss als dritte Parkierungsebene mit zusätzlichen 76 Parkfeldern genutzt werden. Die Ein- bzw. Ausfahrt des Parkhauses ist zwischen der Talstation und dem bestehenden, denkmalgeschützten Bildstock "Husmatt" vorgesehen. B. Am 16. November 2012 erteilte der Gemeinderat Schwyz die Bewilligung für den Neubau der Parkierungsanlage und wies die Einsprachen ab. Gleichzeitig eröffnete er die kantonale Baubewilligung, die das Amt für Raumentwicklung des Kantons Schwyz (ARE/SZ) am 29. Oktober 2012 erteilt hatte. Darin wurden insbesondere drei Einfahrtsbewilligungen in die Kantonsstrasse (Rickenbachstrasse) - für das Parkhaus, die Notausfahrt Parkhaus und die verlegte Hofzufahrt KTN 2052 - unter Auflagen erteilt und die Unterschreitung des Strassenabstands bewilligt. Am 17. Juli 2013 erteilte das Bundesamt für Verkehr (BAV) die seilbahnrechtliche Konzession und die Plangenehmigung für die Umlaufkabinenbahn Rickenbach-Rätigs-Rotenfluh. Diese erwuchs unangefochten in Rechtskraft. C. Gegen die Baubewilligung für die Parkierungsanlage erhoben A._, B._ und C._ Verwaltungsbeschwerde an den Regierungsrat des Kantons Schwyz. Dieser wies die Beschwerde am 2. Juli 2013 ab. Das Verwaltungsgericht des Kantons Schwyz wies die dagegen erhobene Beschwerde der Einsprecher am 27. November 2013 teilweise gut und wies die Sache an den Regierungsrat zurück, um im Sinne der Erwägungen ergänzende Abklärungen und eine anschliessende Neubeurteilung zum bergseitigen Einlenkradius der Parkhauseinfahrt vorzunehmen. Gestützt auf zusätzliche Abklärungen des kantonalen Tiefbauamts wies der Regierungsrat (unter Ausstand von Regierungsrat Othmar Reichmuth) die Verwaltungsbeschwerde am 24. Juni 2014 ab. Die dagegen erhobene Beschwerde der Einsprecher wies das Verwaltungsgericht am 29. Oktober 2014 ab. D. Dagegen gelangten A._, B._ und C._ am 9. Dezember 2014 mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen, die Entscheide des Verwaltungsgerichts vom 27. November 2013 und vom 29. Oktober 2014 seien aufzuheben und die Bewilligungssache zur Neubeurteilung, eventuell zur Neuausschreibung des Bewilligungsgesuchs, an den Gemeinderat Schwyz zurückzuweisen. E. Das Verwaltungsgericht, der Regierungsrat und das ARE/SZ, der Gemeinderat Schwyz und die Rotenfluebahn Mythenregion AG (vormals Seilbahn Rickenbach-Rothenfluh; im Folgenden: die Beschwerdegegnerin) schliessen auf Abweisung der Beschwerde. Im weiteren Schriftenwechsel halten die Parteien an ihren Anträgen fest.