Sachverhalt:
A. Die Firma X._ AG war seit ihrer Gründung im Jahr 2000 der Ausgleichskasse des Kantons Zürich als beitragspflichtige Arbeitgeberin angeschlossen und rechnete mit dieser die paritätischen Beiträge ab.
B._ war seit Beginn und bis zur Auflösung der AG als Mitglied des Verwaltungsrats mit Einzelunterschrift im Handelsregister eingetragen. Am ... 2001 trat S._ als weiteres Mitglied dem Verwaltungsrat bei; er verfügte über Kollektivunterschrift zu zweien. Bis zu seinem Austritt am ... 2006 war B._ Präsident des Verwaltungsrats.
Mit Verfügung vom ... 2007 eröffnete der Konkursrichter des Bezirksgerichts A._ den Konkurs über die Gesellschaft. Das Konkursverfahren wurde mit Verfügung vom ... 2008 für geschlossen erklärt und die Gesellschaft von Amtes wegen gelöscht. Gemäss Verlustausweis infolge Konkurses blieben Forderungen von Fr. 1'052'857.90 und gemäss Kontoauszug vom 11. November 2009 bundes- und kantonalrechtliche Sozialversicherungsbeiträge (einschliesslich Mahngebühren, Veranlagungs- und Betreibungskosten sowie Verzugszinsen) von Fr. 1'053'452.- ungedeckt.
Mit Verfügungen vom 3. Juli 2008 verpflichtete die Ausgleichskasse B._ und S._ zur Leistung von Schadenersatz, B._ in der Höhe von Fr. 1'052'857.90 und S._ in der Höhe von Fr. 877'097.-, je solidarisch bis zum Betrag von Fr. 877'097.-. Die dagegen gerichteten Einsprachen hiess die Ausgleichskasse teilweise gut; sie reduzierte den von B._ zu leistenden Betrag auf Fr. 1'009'498.10 und den von S._ zu leistenden Betrag auf Fr. 875'380.35 (Entscheide vom 9. September 2009).
B. Beschwerdeweise beantragten B._ und S._ (je separat), der jeweilige Einspracheentscheid sei aufzuheben und es sei festzustellen, dass sie nicht zur Leistung von Schadenersatz verpflichtet seien; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das Sozialversicherungsgericht des Kantons Zürich vereinigte die beiden Verfahren und wies die Beschwerden mit Entscheid vom 17. Juni 2011 ab.
C. B._ und S._ lassen Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, der kantonale Entscheid sei aufzuheben und es sei feststellen, dass sie nicht zur Leistung von Schadenersatz verpflichtet seien. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Es sei ihnen ein angemessener Ersatz für die Parteikosten zuzusprechen, dies alles unter Kostenfolgen zu Lasten der Staatskasse. Weiter ersuchen sie darum, der Beschwerde die aufschiebende Wirkung zu erteilen.
Die Ausgleichskasse verzichtet auf eine Vernehmlassung unter Hinweis auf ihre im kantonalen Verfahren eingereichte Stellungnahme und den vorinstanzlichen Entscheid. Das Bundesamt für Sozialversicherungen lässt sich nicht vernehmen.
D. Mit Verfügung vom 12. Oktober 2011 hat die Instruktionsrichterin der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Immerhin prüft es grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (Art. 42 Abs. 1 und 2 BGG; <ref-ruling> E. 1.4.1 S. 254). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG) und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1 BGG).
2. 2.1 Der Ausgleichskasse ist als Folge der Missachtung der Vorschriften betreffend die Pflicht zur Abrechnung und Bezahlung der paritätischen Beiträge (Art. 14 Abs. 1 AHVG und Art. 34 ff. AHVV) durch die konkursite Firma ein Schaden entstanden. Das ist unbestritten. Dieses Verhalten ist den verantwortlichen Organen grundsätzlich als qualifiziertes Verschulden zuzurechnen (<ref-ruling> E. 4b S. 244), was die volle Schadenersatzpflicht nach sich zieht (Urteil 9C_152/2009 vom 18. November 2009 E. 5.2, in: SVR 2010 AHV Nr. 4 S. 11), sofern der Schaden in einem adäquaten Kausalzusammenhang damit steht, keine Rechtfertigungs- oder Exkulpationsgründe gegeben sind (<ref-ruling> E. 4a S. 406; <ref-ruling> E. 1 S. 201) und die Ausgleichskasse kein Mitverschulden trifft (<ref-ruling>).
2.2 Die Beschwerdeführer anerkennen die Höhe des ihnen anzurechnenden Schadensbetrages (Beschwerdeführer 1: Fr. 1'009'498.10; Beschwerdeführer 2: Fr. 875'380.35). Sie machen jedoch geltend, sie hätten sich nicht pflichtwidrig verhalten, weil sie an eine Wende bei der Firma X._ AG hätten glauben dürfen. Auf jeden Fall aber habe das Verhalten der Ausgleichskasse den Kausalzusammenhang zwischen ihrem Verschulden und dem eingetretenen Schaden unterbrochen oder sei zumindest im Sinne eines Haftungsreduktionsgrundes zu berücksichtigen. Die Vorinstanz habe den massgeblichen Sachverhalt im Zusammenhang mit der Beurteilung eines allfälligen Mitverschuldens der Ausgleichskasse unrichtig und unvollständig wiedergegeben. Bundesrechtswidrig sei sie davon ausgegangen, ein Fehlverhalten der Ausgleichskasse in den Jahren 2000 bis 2003 sei nicht geeignet gewesen, zur Entstehung oder Verschlimmerung des Schadens beizutragen, weil der massgebliche Schaden erst im Laufe des Jahres 2004 bzw. in der Zeit danach entstanden sei. Die Vorinstanz verstosse gegen Bundesrecht, wenn sie für Verletzungen des Legalitätsprinzips und die Entstehung des Schadens ein zeitliches Zusammenfallen voraussetzte. Des Weiteren seien im angefochtenen Entscheid eine Vielzahl von Pflichtverletzungen der Ausgleichskasse nicht gewürdigt worden. Die Ausgleichskasse trage ein massgebliches Mitverschulden am entstandenen Schaden.
3. 3.1 Es steht fest und ist unbestritten, dass die Firma bereits in den ersten Jahren ihrer Geschäftstätigkeit wiederholt gemahnt und betrieben werden musste, ihren Verpflichtungen damals jedoch letztlich nachgekommen ist. Die Vorinstanz stellte dazu fest, dass die Fristen des am 16. Mai 2003 bewilligten Zahlungsaufschubes für die definitiven Beiträge des Jahres 2002 und die Fristen des am 30. März 2004 bewilligten Zahlungsaufschubes für die definitiven Beiträge des Jahres 2003 grundsätzlich eingehalten worden seien. Die finanziellen Probleme der Firma X._ AG seien erst Ende des Jahres 2004 und im Laufe des Jahres 2005 auch gegenüber der Ausgleichskasse sichtbar geworden, indem die Firma nicht mehr lediglich für die definitiv festgesetzten Beiträge des Vorjahres einen Zahlungsaufschub beantragt habe, sondern (neu) auch die laufenden Akontozahlungen nicht mehr regelmässig entrichtet und auch dafür um Zahlungsaufschub ersucht habe.
Die Beschwerdeführer bringen nichts vor, was diese Feststellungen als offensichtlich unrichtig erscheinen lässt. Dass einige Zahlungen des bewilligten Aufschubs mit Verspätungen von einem bis sieben Tagen erfolgten, wie die Beschwerdeführer geltend machen, lässt die Feststellung der grundsätzlichen Einhaltung der Fristen (im Sinne einer terminnahen Erfüllung) nicht als offensichtlich unrichtig erscheinen, beinhaltet diese Ausdrucksweise doch geringfügige terminliche Abweichungen. Im Übrigen legen die Beschwerdeführer nicht dar, inwieweit ihre Rügen für den Ausgang des Verfahrens entscheidend sein sollen, was indessen Voraussetzung für eine Berichtigung des vorinstanzlichen Sachverhaltes wäre (vgl. E. 1 hiervor).
3.2 Nach den verbindlichen Feststellungen im angefochtenen Entscheid war die Aktion der Firma Y._ vom Frühjahr 2004 massgeblicher Auslöser der Krise bei der Firma X._ AG. Es wurden Sofortmassnahmen eingeleitet und verschiedene Sanierungsschritte unternommen. Die Sanierungsbemühungen dauerten im Jahr 2006 an (vgl. Geschäftsbericht 2005 vom 17. Juli 2006), wobei ab 2006 ein Verkauf der Firma im Vordergrund stand. Dass die Vorinstanz angesichts dieser Verhältnisse zum Ergebnis gelangte, bei objektiver Betrachtung habe nicht von nur vorübergehenden Zahlungsschwierigkeiten ausgegangen werden können, ist nicht zu beanstanden. Nicht entscheidend ist, dass die Beschwerdeführer, wie sie vorbringen, ernsthaft an eine Wende glaubten. Denn es genügt als Rechtfertigung oder Entschuldigung für die Nichtbezahlung von Sozialversicherungsbeiträgen nicht, dass (subjektiv) Hoffnung auf eine Sanierung des Unternehmens besteht. Verlangt ist vielmehr, dass die Ausstände innert nützlicher Frist beglichen werden können, was wiederum bedingt, dass konkrete, objektive Anhaltspunkte dafür bestehen, dass das Unternehmen in absehbarer Zeit saniert werden kann und wieder zahlungsfähig wird (Urteil H 163/06 vom 11. Juni 2007 E. 4.4; H 394/01 vom 19. November 2003 E. 6.2.3.). Solche konkreten Anhaltspunkte sind nicht ersichtlich.
3.3 Die Vorinstanz verneinte ein Mitverschulden der Ausgleichskasse, welches zu einer Herabsetzung der Schadenersatzforderung führen könnte (<ref-ruling>), mit der Begründung, die Kasse habe sich bis zur Gewährung des Zahlungsaufschubs am 4. August 2005 nicht grob pflichtwidrig verhalten und in Bezug auf die ab August 2005 geschuldeten Akontobeiträge könne ihr - angesichts der Tatsache, dass die Firma immer wieder erhebliche Zahlungen geleistet habe - nicht vorgeworfen werden, dass sie die Vollstreckung nicht mit letzter Konsequenz durchgesetzt habe.
3.3.1 Die nicht offensichtlich unrichtigen und daher für das Bundesgericht verbindlichen vorinstanzlichen Feststellungen vermitteln indessen, insbesondere was die Einforderung der Rückstände des Jahres 2004 und der Akontobeiträge des Jahres 2005 anbelangt, ein anderes Bild: Obwohl die Firma schon in der Vergangenheit wiederholt gemahnt und betrieben werden musste und im Jahr 2003 eine Lohnsumme zur Ausrichtung gelangte, welche mehr als 50 % höher als die den Akontobeiträgen zugrundeliegende Lohnsumme war, zog die Beschwerdegegnerin bloss in Erwägung, die für das Jahr 2004 geschuldeten Akontozahlungen anzupassen, beliess diese aber letztlich auf deutlich zu tiefem Niveau, so dass gemäss Schlussrechnung (betreffend das Jahr 2004) vom 18. Februar 2005 nachzuzahlende Beiträge in der Höhe von Fr. 428'172.- resultierten. Am 30. März 2004 bewilligte sie einen Zahlungsaufschub für die Nachforderung für 2003 von Fr. 376'143.55. Erst am 19. Juli 2004 - und damit vorschriftswidrig nicht unverzüglich (Art. 34a Abs. 1 AHVV) - mahnte sie die Akontobeiträge für den Monat Mai 2004, am 21. Februar 2005 jene von November 2004. Ungeachtet dessen, dass die Firma nicht in der Lage war, die Akontozahlungen für Januar und Februar 2005 (termingerecht) zu leisten (vgl. Mahnungen vom 21. März und 18. April 2005), gewährte die Beschwerdegegnerin am 15. März 2005 einen Zahlungsaufschub für die Nachforderung für das Jahr 2004, ohne dass die finanzielle Bedrängnis vertieft dargelegt worden wäre; dabei unterliess sie es auch zu prüfen, ob die laufenden Beiträge entrichtet werden können, was gemäss Art. 34b Abs. 1 AHVV indessen vorausgesetzt wäre und wozu angesichts der zum damaligen Zeitpunkt bereits ausstehenden Akontobeiträge (November 2004, Januar und Februar 2005) Anlass bestanden hätte. Dass die Kasse die Akontobeiträge schliesslich doch noch Mitte 2005 der höheren Lohnsumme anpasste, nützte unter diesen Umständen wenig. Die Abschlagszahlungen für Mai und Juni 2005 (Abzahlungsplan vom 15. März 2005) mussten zugunsten betriebener Akontozahlungen für November 2004 und Februar 2005 ausgesetzt werden. Obwohl per Ende Juli 2005 Beiträge in der Höhe von Fr. 770'351.90 ausstehend waren, unterliess es die Ausgleichskasse pflichtwidrig, die Einhaltung der Ratenzahlungen und die weiteren Akontozahlungen ab 1. August 2005 eng zu überwachen. Nachdem am 4. August 2005 ein neuer Tilgungsplan vereinbart worden war, welcher von Fr. 40'000.- auf Fr. 25'000.- reduzierte Abschlagszahlungen und einen Abzahlungszeitraum von mehr als zwei Jahren vorsah, gingen keine laufenden Akontozahlungen mehr ein. Erst am 23. Januar 2006 mahnte die Kasse die Akontobeiträge für die Zeit von August bis November 2005. Als die Arbeitgeberin mit einem erneuten Abzahlungsvorschlag an die Kasse gelangte, gewährte diese am 3. Februar 2006 einen weiteren Zahlungsaufschub, allerdings vorschriftswidrig (vgl. Art. 34b Abs. 1 AHVV) ohne eine sofortige Zahlung zu verlangen und wiederum ohne nähere Informationen zur finanziellen Situation des Unternehmens einzuholen. Obwohl bereits die erste, per 28. Februar 2006 zu erbringende Rate gemahnt werden musste (Mahnung vom 15. März 2006) und die zweite Rate innert der vereinbarten Frist (31. Mai 2006) nicht geleistet wurde, blieb die Kasse vorerst untätig. Am 20. Februar 2006 mahnte sie die Beiträge für Dezember 2005; am 22. März 2006 leitete sie für die Beiträge für November und Dezember 2005 die Betreibung ein. Ab Juni 2006 wurde der Abzahlungsplan vom 4. August 2005 nicht mehr eingehalten; die Beschwerdegegnerin mahnte die Firma auch dafür mit Verspätung. Auch mit der Mahnung der für Januar 2006 geschuldeten Akontobeiträge liess sich die Ausgleichskasse bis am 20. März 2006 Zeit; am 20. April 2006 folgte die Betreibung. Weitere Mahnungen betrafen die Monate Februar bis Juni 2006, welche Beiträge alsdann grösstenteils bezahlt wurden. Am 23. August 2006 leitete die Kasse verschiedene Betreibungen ein, unter anderem für eine Forderung vom März 2005. Am 28. August 2006 stellte sie ein Fortsetzungsbegehren. Mit E-Mail vom 14. September 2006 ersuchte die Firma unter Hinweis auf Sanierungsmassnahmen um einen Mahn- und Betreibungsstopp. Am 1. November 2006 gewährte die Kasse einen weiteren Zahlungsaufschub (inzwischen aufgelaufener Betrag: Fr. 845'333.45). Die Akontobeiträge von August bis Dezember 2006 wurden bezahlt, wenn teilweise auch mit Verspätung. Im Februar 2007 leitete die Kasse eine weitere Betreibung ein. Am 30. Januar und 15. März 2007 erliess sie Verfügungen, in denen sie die Lohnbeiträge festlegte und die in den Betreibungen erhobenen Rechtsvorschläge beseitigte; weitere Mahnungen und Betreibungen folgten.
Mit ihrer Passivität resp. schleppenden Vorgehensweise bei der Beitragseintreibung, namentlich der Rückstände aus dem Jahr 2004 und der Akontozahlungen für das Jahr 2005, insbesondere mit dem wiederholten Zuwarten, ausstehende Beiträge zu mahnen (und zu betreiben), sowie der wiederholten (vorschriftswidrigen) Gewährung von Zahlungsaufschüben, hat die Kasse elementare Vorschriften des Beitragsbezugs missachtet, was eine grobe Pflichtverletzung darstellt. Daran vermag nichts zu ändern, dass die Beschwerdegegnerin im Jahr 2006 darum besorgt war, ein weiteres Anwachsen der Beitragsschuld zu vermeiden, hätte dies doch bereits im Jahr 2005 vordringliches Ziel sein sollen. Ebenso wenig führt die von der Vorinstanz hervorgehobene Tatsache, dass die Firma immer wieder erhebliche Beitragszahlungen geleistet hat, zu einer anderen Beurteilung, wäre nämlich schon angesichts der Höhe des Beitragsausstandes (per Ende Juli 2005: Fr. 770'351.90) ein engmaschigeres und konsequenteres Vorgehen dringend angezeigt gewesen (Urteil H 38/03 vom 27. Januar 2004 E. 5).
3.3.2 Der von den Beschwerdeführern zu leistende Schadenersatz ist nur dann und soweit herabzusetzen, als das pflichtwidrige Verhalten der Ausgleichskasse für die Entstehung oder Verschlimmerung des Schadens kausal war (<ref-ruling> E. 3c S. 189). Auch wenn sich die Auswirkungen des pflichtwidrigen Verhaltens der Kasse auf den Schaden im Einzelnen nicht bestimmen lassen, ist mit überwiegender Wahrscheinlichkeit davon auszugehen, dass der Schaden geringer ausgefallen wäre, wenn die Ausgleichskasse pflichtgemäss und rechtzeitig (spätestens ab August 2005 [damals ausstehende Beitragsschuld: Fr. 770'351.90]) die erforderlichen Massnahmen zum Beitragsbezug ergriffen hätte, weshalb der adäquate Kausalzusammenhang zwischen dem pflichtwidrigen Verhalten und der Verschlimmerung des Schadens zu bejahen ist. Zu einer Unterbrechung des Kausalzusammenhanges kommt es - entgegen der in der Beschwerde vertretenen Auffassung - jedoch nicht, bleibt doch das pflichtwidrige Verhalten der Gesellschaftsorgane klare Mitursache des Beitragsverlusts.
3.3.3 Im Hinblick darauf, dass die Beitragsausstände im Juli 2005 rund Fr. 3⁄4 Mio. betrugen, wovon rund 350'000.- auf die Nachforderung für das Jahr 2004 entfiel, und sich der Beitragsverlust schliesslich auf über Fr. 1 Mio. bzw. Fr. 900'000.- belief, rechtfertigt es sich unter Berücksichtigung der gesamten Umstände, den Schadenersatz ermessensweise auf rund die Hälfte des geschuldeten Betrages herabzusetzen, d.h. für den Beschwerdeführer 1 auf Fr. 500'000.- und für den Beschwerdeführer 2 auf Fr. 450'000.-.
4. Dem Ausgang des Verfahrens entsprechend haben die Beschwerdeführer und die Ausgleichskasse die Gerichtskosten je zur Hälfte zu tragen (Art. 66 Abs. 1 und 2 BGG). Die Kasse hat den Beschwerdeführern eine reduzierte Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 17. Juni 2011 und der Einspracheentscheid der Ausgleichskasse des Kantons Zürich vom 9. September 2009 werden insoweit abgeändert, als der Beschwerdeführer 1 verpflichtet wird, der Beschwerdegegnerin Schadenersatz im Betrag von Fr. 500'000.- zu bezahlen, und der Beschwerdeführer 2 verpflichtet wird, ihr Schadenersatz im Betrag von Fr. 450'000.- zu bezahlen, je solidarisch bis zum Betrag von Fr. 450'000.-.
2. Die Gerichtskosten von Fr. 20'000.- werden je zur Hälfte den Beschwerdeführern - dem Beschwerdeführer 1 im Umfang von Fr. 5'300.-, dem Beschwerdeführer 2 im Umfang von Fr. 4'700.- - und der Beschwerdegegnerin auferlegt. Der Anteil der Beschwerdeführer ist durch die geleisteten Kostenvorschüsse von Fr. 15'000.- (Beschwerdeführer 1) und Fr. 14'000.- (Beschwerdeführer 2) gedeckt. Die Differenzbeiträge von Fr. 9'700.- (Beschwerdeführer 1) und Fr. 9'300.- (Beschwerdeführer 2) werden zurückerstattet.
3. Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit je Fr. 1'400.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Zürich zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 31. Mai 2012
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Keel Baumann