Sachverhalt: A. Am 3. Dezember 1976 beschloss die Gemeinde Sils i.E./Segl den Quartierplan Seglias, der am 12. April 1977 von der Regierung Graubünden genehmigt wurde (im Folgenden: Quartierplan 1977). Der damals neu geschaffenen Parzelle Nr. 2863 wurde eine realisierbare Bruttogeschossfläche (BGF) von 283 m2 zugewiesen. Im Quartiergestaltungsplan wurde hierfür ein Baufeld festgelegt, das auf drei Seiten mit einer "Bebauungslinie verbindlich" und auf der Westseite mit einer "Bebauungslinie hinweisend" markiert war. Im Jahr 2007 erfolgte eine Revision des Quartierplans Seglias (im Folgenden: Quartierplan 2007). Für Parzelle Nr. 2863 wurde die Bezeichnung der westlichen Baulinie geändert, indem "hinweisend" durch "verbindlich" ersetzt wurde. B. Am 17. Februar 2011 erwarb der in Rüschlikon wohnhafte Y._ die Parzelle Nr. 2863. Er reichte am 1. April 2011 ein Baugesuch für ein Wohnhaus mit zwei Wohnungen ein. Das geplante Gebäude sollte 4.3 m über die westliche Baulinie ragen. Am 20. Juni 2012 reichte er ein abgeändertes Baugesuch ein, wonach der Baukörper nur noch 1.05 m über die Baulinie ragt, dafür aber höher in Erscheinung tritt. Das abgeänderte Projekt sieht im unteren Geschoss eine Erstwohnung und im Obergeschoss eine Zweitwohnung vor; für den Fall, dass keine Zweitwohnung bewilligt werden könne, erklärte sich der Baugesuchsteller damit einverstanden, beide Wohnungen ausschliesslich als Erstwohnung zu nutzen. Gegen das Bauvorhaben erhoben u.a. die Stockwerkeigentümer der östlich angrenzenden Parzellen Nrn. 2882, 2883 und 2884 (X._ A, B und C) Einsprache. Am 22. August 2012 wies der Gemeindevorstand Sils i.E./Segl die Einsprache ab und entsprach dem (abgeänderten) Baugesuch mit Auflagen und Bedingungen. U.a. wurde der Bauherr verpflichtet, den gesamten neuen Wohnraum auf Parzelle Nr. 2863 der orstansässigen Bevölkerung als Erstwohnraum i.S.v. Art. 71 des Baugesetzes der Gemeinde Sils i.E./Segl vom 18. November 2010 (BauG) zur Verfügung zu stellen. Der Bauherr habe zudem vor Baubeginn folgenden Revers zu unterzeichnen: "Der unterzeichnete Bauherr verpflichtet sich, die Baulinienüberschreitung zu beseitigen, falls der über die Baulinie hinausgehende Grundstückstreifen für eine öffentliche Erschliessungsanlage in Anspruch genommen werden muss und dafür die Beseitigung des über die Baulinie hinausgehenden Gebäudeteils notwendig ist. Der Bauherr hat diese Verpflichtung an allfällige Rechtsnachfolger zu überbinden." C. Dagegen erhoben die Einsprecher am 14. September 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses wies die Beschwerde am 21. November 2012 ab. D. Gegen den verwaltungsgerichtlichen Entscheid haben die im Rubrum genannten Einsprecher am 1. Februar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Sache sei an die Vorinstanz zurückzuweisen, zur Aufhebung der Baubewilligung, eventuell zur Ergänzung des Sachverhalts und zur Neuentscheidung. E. Die Gemeinde Sils/Segl schliesst auf Abweisung der Beschwerde. Y._ (im Folgenden: der Beschwerdegegner) und das Verwaltungsgericht beantragen Abweisung der Beschwerde, soweit darauf einzutreten sei. Im weiteren Schriftenwechsel halten die Beteiligten an ihren Anträgen fest. F. Am 6. März 2013 wurde der Beschwerde die aufschiebende Wirkung erteilt.