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 <ref-law> und die willkürliche Anwendung von kantonalem Gesetzesrecht sowie "im Sinne einer Verfassungsbeschwerde gemäss <ref-law>" die Verletzung des Willkürverbots nach <ref-law> 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.

Erwägungen:
1. 1.1 Gestützt auf <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund (<ref-ruling> E. 1.2 S. 251).
1.2 Anfechtbar ist allerdings nur das Urteil des Verwaltungsgerichts (sog. Devolutiveffekt); dem Antrag der Beschwerdeführer auf Aufhebung des Bau- und Einspracheentscheids der Gemeinde Arosa kann daher von vornherein nicht stattgegeben werden. Immerhin gelten die Entscheide der unteren Instanzen als inhaltlich mitangefochten (vgl. <ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441).
1.3 Nach <ref-law> beurteilt das Bundesgericht Verfassungsbeschwerden gegen Entscheide letzter kantonaler Instanzen nur, soweit keine Beschwerde nach Art. 72-89 BGG zulässig ist. Soweit die Beschwerdeführer ihre Beschwerde im Hinblick auf die erhobene Willkürrüge als solche "im Sinne einer Verfassungsbeschwerde gemäss <ref-law>" bezeichnen, ist dies nicht weiter massgeblich, erweist sich die Willkürrüge doch schon im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten als zulässig, was die subsidiäre Verfassungsbeschwerde ausschliesst.
2. 2.1 Die Beschwerdelegitimation richtet sich nach <ref-law>. Die beschwerdeführenden Stockwerkeigentümergemeinschaften sind Adressatinnen des angefochtenen Entscheids. Die die Stockwerkeinheiten enthaltenden Gebäude grenzen an das Gelände des umstrittenen geplanten Bauprojekts. Die Stockwerkeigentümer sind als Nachbarn durch den angefochtenen Entscheid damit besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Die Beschwerdeführer sind daher grundsätzlich zur Beschwerde legitimiert.
2.2 Eine Stockwerkeinheit wurde inzwischen verkauft, und die neuen Eigentümer sind als Rechtsnachfolger an die Stelle ihres Vorgängers getreten; als solche sind sie ebenfalls beschwerdeberechtigt, auch wenn sie nicht selbst am vorinstanzlichen Verfahren beteiligt waren, da ihnen diese Möglichkeit gar nicht offen gestanden war und ihr Rechtsvorgänger am Verfahren teilgenommen hatte (vgl. <ref-law>).
2.3 Die Gemeinde bestreitet allerdings, dass die Beschwerdeführer legitimiert sind, insoweit Beschwerde zu erheben, als sie das Parkplatzkonzept und die hindernisfreie Zugänglichkeit des Bauprojekts in Frage stellen.
2.3.1 Als Nachbarn sind die Beschwerdeführer indessen berechtigt, gegen den angefochtenen Entscheid über die strittige Baubewilligung wegen angeblicher Missachten des einschlägigen Baurechts Beschwerde zu führen. Sie können dabei auch das vorgesehene Parkierungskonzept und die behindertengerechte Ausgestaltung des Bauprojekts als bundesrechtswidrig anfechten.
2.3.2 Nicht einzugehen ist im Übrigen auf das Vorbringen der Gemeinde, die Beschwerdeführer seien aus gleichem Grunde schon vor dem Verwaltungsgericht nicht berechtigt gewesen, dieselben Rügen vorzutragen, nachdem die Gemeinde den vorinstanzlichen Entscheid nicht angefochten hat.
3. 3.1 Nach <ref-law> dürfen neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt. Soweit sich die Verfahrensbeteiligten auf neue Erkenntnisse wie insbesondere Erkundigungen bei anderen Gemeinden beziehen, die erst eingeholt bzw. zu den Akten gegeben wurden, nachdem der angefochtene Entscheid ergangen war, kann darauf nicht eingegangen werden, da nicht erst das vorinstanzliche Urteil dazu Anlass gegeben hat.
3.2 Gemäss <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Deren Sachverhaltsfeststellung kann nur auf Rüge hin oder von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer gravierenden Rechtsverletzung (im Sinne von <ref-law>) beruht (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
3.2.1 Die Beschwerdeführer machen insbesondere geltend, das Verwaltungsgericht habe es ohne weitere Begründung als notorisch bezeichnet, dass ein Pflegeheim keinen erheblichen Publikumsverkehr mit sich bringe, und insoweit den massgeblichen Sachverhalt offensichtlich unrichtig festgestellt.
3.2.2 Die von den Beschwerdeführern angerufene Feststellung des Verwaltungsgerichts steht jedoch nicht isoliert im angefochtenen Entscheid. So wird im unmittelbaren Zusammenhang mit der Aussage der Notorietät ein Vergleich mit anderen öffentlichen Bauten wie einem Hallenbad oder Eisstadion gezogen. Weiter vorne in der gleichen Urteilserwägung wird überdies ausgeführt, die Gemeinde habe gestützt auf die Erfahrungen mit dem Betrieb des heutigen Pflegeheims und anderen Pflegeheimen nachvollziehbar dargelegt, dass der mit dem Betrieb eines solchen verbundene Parkplatzbedarf in der Praxis wesentlich kleiner sei, als dies bei einer vergleichbaren Nutzfläche für Wohnbauten zutreffe. Es handelt sich bei der vorinstanzlichen Feststellung des geringeren Parkplatzbedarfs für das geplante Pflegeheim demnach nicht um eine solche, die auf reiner Notorietät beruhte, sondern auch auf Erfahrungen in anderen Fällen zurückging, wobei diese Erfahrungen Prozessthema bildeten. Die angefochtene Feststellung des Verwaltungsgerichts ist mithin nicht unhaltbar bzw. offensichtlich unrichtig.
3.2.3 Auch die übrigen tatsächlichen Feststellungen des Verwaltungsgerichts sind mit Blick auf Art. 97 Abs. 1 und Art. 105 BGG nicht zu beanstanden und für das Bundesgericht verbindlich.
4. 4.1 Die Beschwerdeführer rügen, der angefochtene Entscheid verstosse gegen Art. 21 Abs. 1 RPG, wonach die Nutzungspläne für jedermann verbindlich sind, sowie gegen das Legalitätsprinzip nach <ref-law>. Ergänzend berufen sich die Beschwerdeführer auf das kantonale und kommunale Recht.
4.2 Das Bundesgericht prüft die Einhaltung des Bundesrechts frei, diejenige des kantonalen und kommunalen Rechts, von hier nicht interessierenden Ausnahmen abgesehen, hingegen nur auf Willkür hin (vgl. <ref-law>). Daran ändert auch das Legalitätsprinzip gemäss <ref-law> nichts (vgl. <ref-ruling> E. 2.1 S. 162 f.). Der angefochtene Entscheid verkennt die grundsätzliche Verbindlichkeit des Zonenplans der Gemeinde Arosa im Sinne von Art. 21 Abs. 1 RPG nicht. Es fragt sich daher einzig, ob die von der Vorinstanz vorgenommene Auslegung und Anwendung des kantonalen und kommunalen Rechts vor dem Willkürverbot standhält.
4.3 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 S. 5; <ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 3.1 S. 473 f.).
4.4 Nach Art. 28 Abs. 1 erster Satz des Raumplanungsgesetzes für den Kanton Graubünden (KRG) vom 6. Dezember 2004 sowie gemäss Art. 42 Abs. 1 des Baugesetzes der Gemeinde Arosa vom 24. November 2002 (nachfolgend: BG) sind Zonen für öffentliche Bauten und Anlagen für öffentliche oder öffentlichen Interessen dienende Bauten und Anlagen bestimmt (vgl. dazu das Urteil des Bundesgerichts 1C_310/2011 vom 10. November 2011). Dass das hier fragliche Pflegeheim der Gemeinde in die Zone für öffentliche Bauten und Anlagen gehört, ist nicht umstritten.
4.5 Gemäss Art. 42 Abs. 2 BG gelten gegenüber angrenzenden Zonen deren Grenz- und Gebäudeabstände sinngemäss, mindestens aber solche von 2.50 m bzw. 5 m. Die übrigen Zonenvorschriften der angrenzenden Zonen sind bei der Erstellung von Bauten und Anlagen angemessen zu berücksichtigen. Art. 44 BG führt die massgeblichen Kennzahlen der verschiedenen Zonen schematisch auf, und die Art. 45 ff. BG enthalten die zugehörigen Begriffsbestimmungen und konkretisierenden Ausführungen.
4.5.1 Bei der Zone für öffentliche Bauten und Anlagen sieht das kommunale Baugesetz keine fest definierten Kennzahlen für die maximale Ausnützungsziffer, Gebäudehöhe und -länge sowie Grenzabstände vor. Für die letzten gilt die Bestimmung von Art. 42 Abs. 2 erster Satz BG, deren Einhaltung hier nicht strittig ist. Für die übrigen Kennziffern sind gemäss Art. 42 Abs. 2 zweiter Satz BG die Vorschriften der angrenzenden Zonen angemessen zu berücksichtigen. Der Gemeinde steht insoweit ein gewisser Spielraum zu, der pflichtgemäss und willkürfrei auszuüben ist. Dabei ist es nicht willkürlich, von einer rein rechnerischen Ermittlung der Durchschnittswerte der Kennziffern aller angrenzenden Zonen, wie dies die Beschwerdeführer verlangen, abzusehen, sondern wie das Verwaltungsgericht auf die konkreten topografischen und baulichen Verhältnisse abzustellen.
4.5.2 Die hier fragliche Bauparzelle verfügt über eine Fläche von 10'024 m2. Sie grenzt im Süden und im Osten fast ausschliesslich und im Norden auf 105 m an die Dorfzone, in der gemäss dem Zonenschema in Art. 44 BG Gebäudelängen von höchstens 50.00 m und Gebäudehöhen von 12.70 m bei Satteldächern und von 13.90 m bei Flachdächern zulässig sind. Im Westen, teilweise auch im Norden auf einer Länge von 13 m und geringfügig im Osten grenzt die Parzelle an die Wohnzone W2 mit einer maximal zulässigen Gebäudelänge von 20 m und -höhe von 10 m. Als Gebäudelänge gilt nach Art. 49 BG die grössere Seite des kleinsten das Gebäude begrenzenden Rechtecks. Mit der grösstmöglichen rechnerischen Variante, die zur Ermittlung des kleinsten Rechtecks nicht auf dessen Länge, sondern auf dessen Fläche abstellt, ergibt sich beim vorgesehenen Pflegeheim eine maximale Gebäudelänge von 60,98 m. Die Beschwerdeführer behaupten zwar, diese betrage mehr als 64 m, doch vermögen sie nicht darzutun, dass die entsprechende Feststellung des Verwaltungsgerichts offensichtlich unrichtig wäre (vgl. E. 3.2).
4.5.3 Die vorgesehene Gebäudelänge von rund 60 m erweist sich gegenüber der in der Dorfzone zulässigen Länge von 50 m als angemessen und jedenfalls nicht unsachlich. Hinsichtlich der Wohnzone W2 mit der maximal zulässigen Länge von 20 m berücksichtigten die Vorinstanzen, dass das geplante Gebäude im Osten durch den Mittelbach und im Süden durch die Alteinstrasse von der Dorfzone getrennt ist und eine angepasste abgewinkelte Form einnimmt. Das von Norden nach Süden abfallende kupierte Gelände trägt zusätzlich dazu bei, die Gebäudeumrisse perspektivisch zu relativieren. Das Projekt nimmt insoweit auf die angrenzende Dorf- und Wohnzone Rücksicht und ist mithin hinsichtlich der Gebäudegrösse nicht unhaltbar.
4.5.4 Analoges gilt für die Gebäudehöhe. Der geplante Neubau hält die in der Dorfzone zulässige Gebäudehöhe von 13.90 m mit Ausnahme der Gebäudeecke im südöstlichen Bereich (gegen die Alteinstrasse bzw. den Mittelbach) ein, wo eine Höhe von 16.02 m erreicht wird. Dabei handelt es sich um eine nicht übermässige Überschreitung des in der Dorfzone geltenden Höchstwertes im tiefstgelegenen Bereich der Bauparzelle, die durch Aufschüttung hätte vermieden werden können. Darauf wurde jedoch aus nachvollziehbaren Gründen verzichtet. Insgesamt beurteilte das Verwaltungsgericht die Gebäudehöhe unter Berücksichtigung der topografischen Verhältnisse und der umliegenden Überbauungen und damit nicht aus unsachlichen Gründen als nicht unangemessen.
4.5.5 Die Ausnützungsziffer schliesslich berechnet sich nach Art. 45 BG. Gestützt darauf ermittelte das Verwaltungsgericht eine anrechenbare Landfläche von 3'294 m2 und eine massgebliche Bruttogeschossfläche von 2'804 m2. Diese Berechnung beruht erneut auf für das Bundesgericht verbindlichen Feststellungen (vgl. E. 3.2) und ist auch im Resultat nicht zu beanstanden. Daraus ergibt sich für das geplante Pflegeheim eine Ausnützungsziffer von 0.85, die unter dem für die Dorfzone geltenden Wert von 0.9 liegt und auch die in der Wohnzone W2 gültige Ziffer von 0.6 nicht übermässig überschreitet. Es ist daher nicht unhaltbar, die Ausnützungsziffer für das Bauprojekt als zulässig zu beurteilen.
4.6 Nach Art. 26 BG sind bei Neubauten, Erweiterungen und bei Zweckänderungen auf der Bauparzelle oder in nächster Nähe auf privatem Boden während des ganzen Jahres zugängliche Abstellplätze für Motorfahrzeuge zu erstellen und dauernd für die Parkierung offen zu halten (Abs. 1). Für je 80 m2 anrechenbare Bruttogeschossfläche, mindestens aber pro Wohnung oder pro Laden, ist ein Autoabstellplatz zu schaffen. Restflächen über 40 m2 sind aufzurunden. Die Baubehörde kann für Geschäftslokale, Gastgewerbebetriebe und andere Objekte mit erheblichem Publikumsverkehr abweichende Vorschriften erlassen. Mindestens zwei Drittel der Pflichtparkplätze sind in Garagen zu erstellen (Abs. 2). Die Baubehörde kann die Eigentümer zum Erwerb von Autoabstellflächen auf fremdem Land oder in einer Gemeinschaftsanlage verpflichten, wenn dies im öffentlichen Interesse liegt. Voraussetzung ist jedoch, dass die Plätze in vertretbarer Distanz liegen und ihre dauernde Verfügbarkeit rechtsgeschäftlich und grundbuchlich sichergestellt ist (Abs. 5).
4.6.1 Mit der vom Verwaltungsgericht geschützten Baubewilligung wurde die Gemeinde Arosa verpflichtet, für das geplante Pflegeheim insgesamt 27 Parkplätze zu erstellen und dauernd offen zu halten, wovon 19 im Parkhaus Ochsenbühl, zwei in einer Einstellgarage im Untergeschoss, sechs im Eingangsbereich mit Zugang von der Alteinstrasse her, davon wiederum zwei in behindertengerechter Ausgestaltung. Die Beschwerdeführer gehen davon aus, bei korrekter Anwendung von Art. 26 BG seien mindestens 35 Pflichtparkplätze bereit zu stellen, und rügen überdies, die Ansiedlung von 19 Plätzen im Parkhaus Ochsenbühl sei nicht zulässig.
4.6.2 Es ist unter den Verfahrensbeteiligten nicht strittig, dass die Anzahl geforderter Parkplätze von 27 die gesetzlich grundsätzlich erforderliche um rund acht unterschreitet. Es trifft auch zu, wie die Beschwerdeführer geltend machen, dass der Wortlaut von Art. 26 Abs. 2 BG eine Abweichung nach unten, im Unterschied zu einer solchen nach oben für besonders verkehrsintensive Bauten, nicht ausdrücklich vorsieht. Das führt aber nicht zwingend zur Unzulässigkeit des verfügten Parkierungsregimes. Die Anforderungen an die gesetzliche Grundlage sind bei der Erleichterung einer gesetzlichen Pflicht grundsätzlich weniger hoch als bei der Begründung bzw. Erschwerung einer solchen. Die fragliche Regelung ist sodann zugeschnitten auf Bauten mit einem üblichen Verkehrsaufkommen. Das Verwaltungsgericht stellte demgegenüber verbindlich (vgl. E. 3.2) fest, dass der mit dem Betrieb eines Pflegeheims verbundene Parkplatzbedarf wesentlich kleiner ist, als dies bei einer vergleichbaren Nutzfläche für Wohnbauten zutrifft. Die Berechnungen der Gemeinde beruhen überdies auf sachlichen Grundlagen. Sie gehen davon aus, dass bei den 40 Heimbewohnern angesichts ihrer Pflegeabhängigkeit kein direkter Bedarf an Parkplätzen besteht und von einem solchen für die Beschäftigten von acht Parkplätzen (40% von rund 20 Angestellten) sowie von fünf Besucherparkplätzen und einem Platz für die spitalexterne Betreuung auszugehen ist. Das Verwaltungsgericht verweist ergänzend darauf, für einen allenfalls ausserordentlichen höheren Spitzenbedarf stünden weitere der Allgemeinheit zugängliche, d.h. nicht speziell gekennzeichnete, Parkplätze im nahen Parkhaus, das insgesamt rund 460 Parkplätze anbietet, zur Verfügung. Dieses ist nur selten ausgelastet, und die zusätzliche Benutzung des Parkhauses stünde insbesondere für eventuell höheren Besucherverkehr an Wochenenden oder Feiertagen offen, wie ihn die Beschwerdeführer in erster Linie befürchten.
4.6.3 Hinsichtlich der 19 im Parkhaus Ochsenbühl vorgesehenen Parkplätze kann es keine Rolle spielen, dass es sich dabei nicht um Parkplätze auf privatem Boden handelt, wie es der auch diesbezüglich auf private Bauprojekte zugeschnittene Wortlaut von Art. 26 Abs. 1 BG an sich vorschreibt. Es erscheint nicht willkürlich, sondern entspricht vielmehr gerade dem Gesetzeszweck, von einer Gesetzesauslegung auszugehen, wonach für ein öffentliches Bauvorhaben ein öffentliches Grundstück beansprucht wird. Im Übrigen erlaubt Art. 26 Abs. 5 BG ebenfalls die Ausgliederung der Parkplätze, wenn dies im öffentlichen Interesse liegt. Angesichts des nicht ausgelasteten bestehenden Parkhauses sowie mit Blick auf die sinnvolle Vermeidung eines überdimensionierten Parkangebots mit entsprechenden Auswirkungen auf den Quartierverkehr erweist sich die Ausgliederung von 19 Parkplätzen als nicht unhaltbar und müsste wenigstens teilweise sogar dem Interesse der Beschwerdeführer selbst entsprechen. Die Baubewilligung wurde überdies mit der Auflage verbunden, sämtliche Pflichtparkplätze grundbuchlich zu sichern, womit auch die entsprechende Anforderung von Art. 26 Abs. 5 BG erfüllt wird. Gemäss derselben Bestimmung müssen ausgegliederte Parkplätze sodann "in vertretbarer Distanz" bzw. nach Art. 26 Abs. 1 BG "in nächster Nähe" liegen. Das fragliche Parkhaus befindet sich in einer Gehwegdistanz von 200 m zum nordseitigen Eingang des geplanten Pflegeheims. Der neu anzulegende Gehweg wird serpentinenartig mit einem maximalen Gefälle von 6% ausgestaltet und ist damit den Insassen, soweit diese davon betroffen sind, Beschäftigen und Besuchern des Pflegeheimes durchaus zuzumuten. Allerdings wird die Gemeinde, insbesondere durch die Erbringung des entsprechenden Winterdienstes, zu gewährleisten haben, dass der Zugang ganzjährig uneingeschränkt benutzbar ist.
4.6.4 Die Beschwerdeführer machen nicht ausdrücklich geltend, einen Zusatzverkehr sowie wildes Parkieren in ihrem Quartier zu befürchten, doch dürfte es auch in diesem Zusammenhang stehen, dass sie das geplante Parkierungskonzept anfechten. Die Gemeinde wird so oder so das Nötige vorzukehren haben, um die Einhaltung des vorgesehenen Parkierungsregimes sicher zu stellen und allfällige negative Auswirkungen auch auf das Quartier der Beschwerdeführer wirkungsvoll zu beschränken.
4.6.5 Insgesamt erweist sich das mit der angefochtenen Baubewilligung bewilligte bzw. verfügte Parkierungskonzept gemessen an den einschlägigen Bestimmungen und den konkreten Verhältnissen demnach nicht als unsachlich und damit willkürlich.
4.7 Schliesslich rügen die Beschwerdeführer die willkürliche Anwendung von Art. 80 KRG, weil der angefochtene Entscheid bzw. das dadurch geschützte Bauprojekt diese kantonale Bestimmung über das behindertengerechte Bauen in krasser Weise missachte. Ob diese Rüge korrekt vorgetragen wurde und insbesondere die Anforderungen an die Begründungspflicht gemäss Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG erfüllt (vgl. dazu <ref-ruling> E. 1.4.1 und 1.4.2 S. 254), ist fraglich, da die Beschwerdeschrift dazu eher allgemein gehalten ist und kaum konkrete Ausführungen enthält, was aber offen bleiben kann. Ansatzweise geht aus der Beschwerdeschrift hervor, dass die Erschliessung des Pflegeheimes nach Auffassung der Beschwerdeführer insbesondere für behinderte Insassen und deren Besucher über den serpentinenartigen Weg vom bzw. zum Parkhaus Ochsenbühl unzumutbar sei. Für Behinderte erfolgt der Zugang zum Pflegeheim indessen vorrangig über die Alteinstrasse, wo ein Eingang mit invalidengerechtem ebenerdigen Zugang, die beiden behindertengerechten Parkplätze sowie die weiteren Parkplätze für Bring- und Abholdienste vorgesehen sind. Diese Lösung entspricht den Empfehlungen der zu diesem Zweck von der Baubehörde freiwillig (vgl. die Kann-Formulierung in Art. 80 Abs. 3 KRG) beigezogenen Fachstelle der Pro Infirmis. Aber auch der Gehweg auf der Nordwestseite des Gebäudes mit einem Gefälle von 6% und seiner serpentinenartigen Ausgestaltung ist für Behinderte nicht unzugänglich, selbst für solche, die auf zusätzliche Hilfsmittel (wie Rollstühle oder Elektrorollstühle) oder auf die Unterstützung durch andere Personen angewiesen sind. Somit ist der angefochtene Entscheid auch mit Blick auf Art. 80 KRG nicht unhaltbar.
4.8 Das Urteil des Verwaltungsgerichts hält demnach vor dem angerufenen Bundesrecht stand und ist namentlich nicht willkürlich.
5. 5.1 Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
5.2 Bei diesem Verfahrensausgang werden die unterliegenden Beschwerdeführer für das bundesgerichtliche Verfahren unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und 5, <ref-law>).
5.3 Die obsiegende Gemeinde Arosa verlangt die Zusprechung einer angemessenen Parteientschädigung und beruft sich dazu auf das kantonale Verfahrensrecht. Dieses gilt indessen nur für den Prozess vor dem Verwaltungsgericht und ist vor Bundesgericht nicht anwendbar. Soweit die Gemeinde Arosa damit zugleich eine Entschädigung für das vorinstanzliche Verfahren beantragen sollte, kann darauf nicht eingegangen werden, da die Gemeinde das vorinstanzliche Urteil nicht angefochten hat. Für das bundesgerichtliche Verfahren ist auf <ref-law> abzustellen, wonach insbesondere Bund, Kantonen und Gemeinden in der Regel keine Parteientschädigung zugesprochen wird, wenn sie in ihrem amtlichen Wirkungskreis obsiegen. Im vorliegenden Fall handelte die - im Übrigen nicht anwaltlich vertretene - Gemeinde Arosa in ihrem amtlichen Wirkungskreis, und es rechtfertigt sich nicht, von der gesetzlichen Regel abzuweichen. Die Beschwerde brachte keinen aussergewöhnlichen Arbeitsanfall mit sich, der den üblichen Rahmen sprengen würde und eine Ausnahme zu begründen vermöchte, auch wenn die Gemeinde insofern, wie sie geltend macht, durchaus einen gewissen Aufwand zu betreiben hatte.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 6'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Gemeinde Arosa und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 29. August 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Aemisegger
Der Gerichtsschreiber: Uebersax