Sachverhalt: A. A.a In der Abstimmung vom 27. September 2009 bewilligte das Stimmvolk der Gemeinde Arosa einen Gesamtkredit von 14 Millionen Franken für die Erstellung eines neuen Pflegeheims auf dem Areal "Ochsenbühl", Parzelle Nr. 128. Die Bauparzelle gehört der Gemeinde Arosa und befindet sich in der Zone für öffentliche Bauten und Anlagen. A.b Am 26. Januar 2011 reichte die Gemeinde Arosa ein Gesuch um Abbruch des bestehenden Stalles sowie um Neuerstellung des Pflegeheimes auf der Parzelle Nr. 128 ein. Vorgesehen war ein Gebäude mit einer Grundfläche von 1'094 m2 als Pflegeheim mit 40 Betten sowie mit zwei Autoabstellplätzen in Garagen und zwei im Freien sowie 23 weiteren im nahe gelegenen Parkhaus "Ochsenbühl". Am 11. Februar 2011 nahm die Beratungsstelle für hindernisfreies Bauen der Pro Infirmis Stellung zum Projekt, beurteilte die gesetzlichen Anforderungen für hindernisfreies Bauen als erfüllt und regte lediglich einige Verbesserung beim Parkierungskonzept an. Nach Durchführung eines Augenscheins bewilligte die Baukommission Arosa am 21./30. März 2011 das Baugesuch unter gleichzeitiger Abweisung der eingegangenen Einsprachen und unter Anpassung der Baueingabe an die Anregungen der Beratungsstelle für das Parkierungskonzept, indem deren Stellungnahme vom 11. Februar 2011 zum integrierenden Bestandteil der Baubewilligung erklärt wurde. Das führte im Wesentlichen zur Auflage, vier zusätzliche Parkplätze, wovon zwei mit behindertengerechter Ausgestaltung, als Kurzzeit-Parkplätze bei der Zufahrt für Bring- und Abholdienste zu erstellen unter gleichzeitiger Reduktion der Anzahl der dem Pflegeheim zugeteilten Parkplätze im Parkhaus auf 19. B. Verschiedene Eigentümer von Stockwerkeinheiten in den benachbarten Liegenschaften "X._" sowie "Y._" erhoben dagegen Einsprache beim Gemeinderat Arosa. Dieser wies die Einsprachen mit Entscheid vom 18./24. Mai 2011 nach Durchführung eines Augenscheines ab. C. Mit Urteil vom 17. November 2011 wies das Verwaltungsgericht, 5. Kammer, des Kantons Graubünden, ebenfalls nach Durchführung eines Augenscheines, eine dagegen eingereichte Beschwerde ab. D. D.a Die Stockwerkeigentümergemeinschaft "X._", bestehend aus A._ und B._, C._ und D._, E._, F._ und G._, H._ und I._ sowie J._, und die Stockwerkeigentümergemeinschaft "Y._", bestehend aus K._ und L._, M._ und N._, O._ und P._ sowie Q._ und R._, führen beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen das Urteil des Verwaltungsgerichts. Sie beantragen im Wesentlichen, dieses Urteil sowie den damit bestätigten Bau- und Einspracheentscheid aufzuheben; eventuell sei die Streitsache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Zur Begründung wird hauptsächlich die unrichtige Feststellung des Sachverhalts sowie die Verletzung von Art. 21 RPG, ein Verstoss gegen das Legalitätsprinzip nach Art. 5 Abs. 1 BV und die willkürliche Anwendung von kantonalem Gesetzesrecht sowie "im Sinne einer Verfassungsbeschwerde gemäss Art. 113 BGG" die Verletzung des Willkürverbots nach Art. 9 BV geltend gemacht. D.b Die Gemeinde Arosa und das Verwaltungsgericht des Kantons Graubünden schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. D.c Die beschwerdeführenden Stockwerkeigentümergemeinschaften liessen sich am 11. Juli 2012 nochmals zur Sache vernehmen. E. Mit Verfügung vom 5. Juni 2012 erteilte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung. 