Sachverhalt:
A.
A.a. Der 1971 geborene A._ war zuletzt bis September 2011 als Hilfsgipser tätig. Im August 2012 meldete er sich erstmals bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Solothurn (fortan: IV-Stelle) traf erwerbliche und medizinische Abklärungen und holte insbesondere ein psychiatrisches Gutachten bei Dr. med. B._ ein (Expertise vom 5. Mai 2015 sowie ergänzende Stellungnahme vom 27. Januar 2016). Unter Verweis darauf verneinte sie mit Verfügung vom 17. August 2016 mangels nachweisbarer krankheitswertiger psychischer Störung einen Leistungsanspruch, was das Versicherungsgericht des Kantons Solothurn mit Urteil vom 26. Juni 2018 und das Bundesgericht mit Urteil 9C_582/2018 vom 7. Januar 2019 bestätigten.
A.b. Im August 2019 meldete sich der Versicherte erneut bei der IV-Stelle zum Leistungsbezug an. Er verwies dabei auf eine schwere, komplexe psychische Beeinträchtigung gemäss einem - im Rahmen eines Strafverfahrens erstellten - psychiatrischen Gutachten des Dr. med. C._ vom 12. November 2018 und mithin auf eine erhebliche gesundheitliche Veränderung seit dem 17. August 2016. Die IV-Stelle holte eine Stellungnahme ihres Regionalen Ärztlichen Dienstes (RAD) ein, der gestützt auf das psychiatrische Gutachten des Dr. med. C._ eine Arbeitsfähigkeit seit spätestens April 2012 verneinte (Beurteilung vom 6. November 2019). M it Vorbescheid vom 23. Januar 2020 stellte sie eine Leistungsablehnung zufolge unveränderten Gesundheitszustands in Aussicht. Nach Einwand des Versicherten leitete die IV-Stelle die Akten am 7. April 2020 im Hinblick auf eine prozessuale Revision an das Bundesgericht weiter und sistierte ihr Verfahren. Auf Nachfrage des Bundesgerichts hin teilte A._ mit, er wünsche keine Eröffnung eines Revisionsdossiers. Daraufhin setzte die Verwaltung ihr Verfahren fort. Mit Verfügung vom 13. Mai 2020 verneinte sie zufolge unveränderten Gesundheitszustands einen Anspruch auf Rente, berufliche Massnahmen sowie Hilflosenentschädigung.
B.
Die hiergegen erhobene Beschwerde wies das Versicherungsgericht des Kantons Solothurn mit Urteil vom 7. Januar 2021 ab.
C.
A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das vorinstanzliche Urteil vom 7. Januar 2021 sei aufzuheben und es seien ihm die geltend gemachten IV-Leistungen (beruflicher Art, Invalidenrente und Hilflosenentschädigung) nach Massgabe eines IV-Grades von mindestens 40 % zuzusprechen. Eventualiter seien ergänzende medizinische und/oder beruflich-konkrete Abklärungen durchzuführen. Ferner sei ihm die unentgeltliche Rechtspflege zu gewähren und Rechtsanwalt Claude Wyssmann als unentgeltlicher Rechtsbeistand einzusetzen.
Die IV-Stelle sowie die Vorinstanz beantragen unter Verweis auf das vorinstanzliche Urteil vom 7. Januar 2021 die Abweisung der Beschwerde. Letztere weist zudem darauf hin, dass sich der Wegfall des Suchtverhaltens des Versicherten aus dem Gutachten des Dr. med. C._ ergebe. Das Bundesamt für Sozialversicherungen (BSV) lässt sich nicht vernehmen. Der Beschwerdeführer äussert sich mit Eingabe vom 4. Juni 2021 abschliessend.

Erwägungen:
1.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 f. BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dennoch prüft es - offensichtliche Fehler vorbehalten - nur die in seinem Verfahren gerügten Rechtsmängel (Art. 42 Abs. 1 und 2 BGG). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>) und kann ihre Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG; zum Ganzen <ref-ruling> E. 4).
2.
Das kantonale Gericht hat die massgeblichen Grundlagen insbesondere zum Vorgehen analog der Revision bei Neuanmeldung (<ref-law> i.V.m. Art. 87 Abs. 2 und 3 IVV) grundsätzlich zutreffend dargelegt. Darauf wird verwiesen.
Voraussetzung für eine Rentenrevision ist die Änderung des Invaliditätsgrades einer rentenbeziehenden Person in einer für den Anspruch erheblichen Weise (<ref-law>). Notwendig ist demnach eine wesentliche Änderung in den tatsächlichen Verhältnissen seit Zusprache der Rente, die geeignet ist, den Invaliditätsgrad und damit den Anspruch zu beeinflussen. Eine hinzugetretene oder weggefallene Diagnose stellt nicht per se einen Revisionsgrund dar, da damit das quantitative Element der (erheblichen) Gesundheitsverbesserung oder -verschlechterung nicht zwingend ausgewiesen ist. Eine weitere Diagnosestellung bedeutet nur dann eine revisionsrechtlich relevante Gesundheitsverschlechterung oder eine weggefallene Diagnose eine verbesserte gesundheitliche Situation, wenn diese veränderten Umstände den Rentenanspruch berühren (<ref-ruling> E. 5.2 mit Hinweisen; Urteil 9C_42/2019 E. 5.2.1).
3.
3.1. Das Versicherungsgericht stellte in Würdigung der medizinischen Akten fest, gemäss Gutachten des Dr. med. C._ lägen insbesondere eine dissoziale Persönlichkeitsstörung (ICD-10 F60.2) sowie eine paranoide Schizophrenie (ICD-10 F20.0) vor. Die Schizophrenie habe erkennbar bereits seit 2012 vorgelegen und die Persönlichkeitsstörung habe jahrelang das Leben des Versicherten geprägt. Es erwog, dabei handle es sich indes um eine abweichende Würdigung des gleichen Sachverhalts im Vergleich zum Gutachten des Dr. med. B._, was unter revisionsrechtlichen Gesichtspunkten nicht ausreiche um eine Veränderung zu belegen. Dies gelte umso mehr, als auch der RAD-Arzt in seiner Stellungnahme vom 6. November 2019 davon ausgehe, dass bereits seit April 2012 keine Arbeitsfähigkeit mehr bestanden habe. Dass zwischen den beiden Gutachten eine früher bestehende Substanzabhängigkeit weggefallen sei, stelle als gesundheitliche Verbesserung bei bereits zuvor verneintem Leistungsanspruch zum vornherein keine leistungsrelevante Veränderung des Gesundheitszustands dar. Die IV-Stelle habe demnach zu Recht einen Leistungsanspruch im Rahmen der Neuanmeldung verneint. Fraglich sei höchstens, ob es sich beim Gutachten des Dr. med. C._ um ein neues Beweismittel gehandelt habe, das eine prozessuale Revision des bundesgerichtlichen Urteils vom 7. Januar 2019 erlaubt hätte, worauf der Beschwerdeführer indes verzichtet habe.
3.2. Der Beschwerdeführer wirft der Vorinstanz im Wesentlichen eine Verletzung von <ref-law> vor, da sie einen Revisionsgrund zu Unrecht verneint habe. Der Wegfall seines früheren Suchtverhaltens bzw. schädlichen Gebrauchs von psychotropen Substanzen (Alkohol, Kokain, Benzodiazepinen) stelle einen solchen dar, habe er doch dazu geführt, dass im ersten Leistungsverfahren die - bereits damals vorliegenden - psychotischen Symptome nicht hätten zugeordnet werden können, so dass eine paranoide Schizophrenie nicht attestiert worden sei.
4.
4.1. Mit der Vorinstanz stellt grundsätzlich - für sich allein genommen - der Wegfall einer gesundheitlichen Beeinträchtigung, mithin eine Verbesserung des Gesundheitszustands, bei zuvor vollumfänglich verneintem Leistungsanspruch, keinen Revisions- bzw. Neuanmeldungsgrund dar (analog der Rechtsprechung, wonach umgekehrt etwa bei Bezug einer ganzen Invalidenrente gesundheitliche Verschlechterungen ebenfalls zu keiner Rentenrevision führen, da sie zum vornherein nicht anspruchserheblich sein können, vgl. zit. Urteil 9C_42/2019 E. 5.3.2; Urteil 9C_107/2019 vom 7. August 2019 E. 5.2.3; ausserdem Urteil 9C_357/2019 vom 17. Dezember 2019 E. 5 zur Unmassgeblichkeit weiterer Verbesserungen bei gesundheitlichen Störungen, die sich bereits zuvor nicht leistungsrelevant auswirkten).
4.2. Dass insofern eine tatsächliche Veränderung eingetreten ist, als mittlerweile beim Beschwerdeführer kein schädlicher Substanzgebrauch bzw. keine Substanzabhängigkeit mehr besteht, stellte das kantonale Gericht - nicht offensichtlich unrichtig, und für das Bundesgericht damit grundsätzlich verbindlich (oben E. 1) - fest, was es im Schriftenwechsel vor Bundesgericht bekräftigt und unbestritten geblieben ist. Der Beschwerdeführer weist zu Recht darauf hin, dass damit - anders als im zit. Urteil 9C_357/2019 zugrunde liegenden Fall - nicht die Verbesserung einer bereits im ersten Leistungsverfahren anspruchsunerheblichen gesundheitlichen Beeinträchtigung geltend gemacht wird. Vielmehr ist der Wegfall einer Tatsache zu beurteilen, die dannzumal zur Beweislosigkeit in Bezug auf eine - nunmehr erkennbare - Erkrankung aus dem schizophrenen Formenkreis geführt hat. Angesichts dessen ist die Feststellung der Vorinstanz offensichtlich unrichtig und zu korrigieren (E. 1 hiervor), wonach die psychiatrischen Gutachter Dres. med. B._ und C._ ihre jeweiligen Einschätzungen gestützt auf denselben Sachverhalt abgegeben hätten. Entsprechend kann auch entgegen dem Versicherungsgericht keine Rede davon sein, dass es sich bei der späteren Diagnosestellung durch Dr. med. C._ um eine - revisionsrechtlich unbeachtliche (etwa: <ref-ruling> E. 2.3) - unterschiedliche Beurteilung eines im Wesentlichen gleich gebliebenen Sachverhalts handle. Aktenkundig und auch der vorinstanzlichen Wiedergabe der medizinischen Akten zu entnehmen ist vielmehr, dass Dr. med. B._ u.a. deshalb keine Schizophrenie zu attestieren vermochte, weil die erhobenen Befunde sich zufolge Konsums psychotroper Substanzen bei möglicher Abhängigkeitsstörung einer eindeutigen Zuordnung entzogen. Demgegenüber basierte das Gutachten des Dr. med. C._ vom 12. November 2018 auf einem Zustand mit offenbar stabiler, mittels regelmässiger Haarproben überwachter Abstinenz. Der Wegfall des Substanzkonsums erlaubte ihm, die - unbestritten im Vergleich zum Vorgutachten im Wesentlichen deckungsgleichen - Befunde nunmehr den Diagnosen einer dissozialen Persönlichkeitsstörung (ICD-10 F60.2) sowie einer paranoiden Schizophrenie (ICD-10 F20.0) zuzuordnen.
4.3. Anlass zu einer Rentenrevision bzw. einer Neuanmeldung gibt grundsätzlich jede wesentliche Änderung in den tatsächlichen Verhältnissen, die geeignet ist, den Invaliditätsgrad und damit den Anspruch zu beeinflussen (oben E. 2). Zu vergleichen sind der Sachverhalt, wie er der letzten Leistungsverfügung zugrunde lag mit demjenigen, der sich im Zeitpunkt der neuerlichen Leistungsverfügung präsentiert (<ref-ruling> E. 3.5.2). Entgegen der Vorinstanz geht die Rechtsprechung dabei keineswegs davon aus, dass nur eine direkt anspruchserhebliche tatsächliche Veränderung des Gesundheitszustands der versicherten Person zur Revision führen kann. Massgebend ist vielmehr das gesamte anspruchserhebliche Tatsachenspektrum. Die Änderung tatsächlicher Natur muss nur - aber immerhin - so beschaffen sein, dass sie sich rechtlich erheblich auf den laufenden Rentenanspruch auswirkt (vgl. Urteil 9C_197/2017 vom 27. November 2017 E. 4.3.2). Dies trifft zu auf Tatsachen, die neu zum Ausschluss eines potenziell die Arbeitsfähigkeit einschränkenden Gesundheitsschadens führen (vgl. zur Rechtslage bei Aggravation bezüglich der Leistungseinschränkung Urteile 8C_380/2019 vom 11. Oktober 2019 E. 4.1; 8C_825/2018 vom 6. März 2019 E. 6.1 mit Hinweisen). Umgekehrt kann Grund für eine Revision oder Neuanmeldung auch sein, dass eine zuvor bestehende Beweislosigkeit - die sich als Ausfluss der materiellen Beweislast grundsätzlich zu Lasten der versicherten Person auswirkt (<ref-ruling> E. 4.3) - entfällt. Es wäre methodendualistisch und somit widersprüchlich, im Rahmen einer erstmaligen Leistungsprüfung Leistungen zu verweigern mit Verweis auf die herrschende Beweislosigkeit bezüglich eines Gesundheitsschadens (zur Bedeutung der medizinischen Befundlage und der Notwendigkeit einer fachärztlich einwandfreien Diagnose einer Gesundheitsbeeinträchtigung als Ausgangspunkt der Anspruchsprüfung vgl. etwa <ref-ruling> E. 5.1) - womit die Beweislosigkeit klarerweise rechts- und anspruchserheblich ist -, später hingegen den Wegfall derselben Beweislosigkeit durch einer veränderten Sachlage nicht als wesentliche Änderung der tatsächlichen Verhältnisse anzuerkennen.
4.4. Fallbezogen ist hier eine Änderung der tatsächlichen Verhältnisse mit überwiegender Wahrscheinlichkeit (zu diesem im Sozialversicherungsrecht üblichen Beweisgrad: etwa <ref-ruling> E. 3.2 mit Hinweis) eingetreten. Ein im Zeitpunkt der leistungsabweisenden Verfügung vom 17. August 2016 noch bestehender Substanzmissbrauch ist weggefallen (E. 4.2 hiervor). Diese tatsächliche Entwicklung stellt zwar als Verbesserung des Gesundheitszustandes für sich allein genommen keinen Neuanmeldungsgrund dar (oben E. 4.1). Es handelt sich indes dabei insoweit um eine wesentliche Änderung der tatsächlichen Verhältnisse, als damit die zuvor herrschende Beweislosigkeit bezüglich (u.a.) der paranoiden Schizophrenie (vgl. dazu bereits Urteil 9C_582/2018 vom 7. Januar 2019 E. 2.3) entfallen ist (soeben E. 4.3). Dass das neu nachweisbare Vorliegen einer solchen Erkrankung zumindest dem Grundsatz nach geeignet ist, den Invaliditätsgrad und damit den Leistungsanspruch des Beschwerdeführers zu beeinflussen, liegt - auch mit Blick auf die von den psychiatrischen Gutachtern erhobenen Befunde - auf der Hand.
4.5. Das im Rahmen eines Strafverfahrens erstellte Gutachten des Dr. med. C._ zeigt nach dem Gesagten nachvollziehbar auf, dass (u.a.) spätestens seit April 2012 eine paranoide Schizophrenie besteht. Entsprechend dem auf die Zwecke des Strafverfahrens bezogenen Gutachtensauftrag - Klärung von Fragen der Schuldfähigkeit und Rückfallgefahr - befasste sich der Experte weder näher mit den funktionellen Einschränkungen des Beschwerdeführers, noch gab er eine begründete Schätzung zu dessen Arbeitsfähigkeit ab. Zur Arbeitsfähigkeit äusserte sich erst der RAD, der sie aufgrund der Akten ohne nähere Begründung als seit April 2012 vollständig aufgehoben betrachtete. Dies reicht als beweiswertige medizinische Entscheidgrundlage offensichtlich nicht aus, fehlt doch insbesondere jede Prüfung der rechtsprechungsgemäss massgeblichen Indikatoren (grundlegend: <ref-ruling>). Indem Vorinstanz und Verwaltung zur Arbeitsfähigkeit des Beschwerdeführers trotz erheblicher Veränderung der tatsächlichen Verhältnisse keine Abklärungen getroffen haben, verletzten sie offensichtlich den Untersuchungsgrundsatz (Art. 43 Abs. 1 bzw. <ref-law>). Die Sache ist an die IV-Stelle zurückzuweisen, damit sie im Rahmen der Neuanmeldung eine psychiatrische Begutachtung (sowie, falls notwendig, weitere Abklärungen) veranlasse und hernach neu verfüge.
4.6. Angesichts des Verfahrensausgangs erübrigen sich Weiterungen zu den im Zusammenhang mit der erstmaligen Prüfung des Anspruchs auf Hilflosenentschädigung erhobenen Rügen ebenso wie solche zur Frage, ob die mit <ref-ruling> geänderte Rechtsprechung bezüglich stoffgebundener Suchterkrankungen einen Revisions- bzw. Neuanmeldungsgrund darstellt.
5.
Hinsichtlich der Prozesskosten gilt die Rückweisung der Sache zu neuem Entscheid (mit noch offenem Ausgang) praxisgemäss als volles Obsiegen der beschwerdeführenden Partei, unabhängig davon, ob sie beantragt oder ob das entsprechende Begehren im Haupt- oder im Eventualantrag gestellt wird (<ref-ruling> E. 6.1; Urteil 8C_68/2021 vom 6. Mai 2021 E. 7.1). Die Beschwerdegegnerin hat daher im vorliegenden Verfahren die Gerichtskosten zu tragen. Dem Versicherten schuldet sie eine Parteientschädigung, die bei Gesuchen um unentgeltliche Rechtspflege praxisgemäss dessen Rechtsvertreter zuzusprechen ist (Art. 66 Abs. 1 und Art. 68 Abs. 1 und 2 BGG; ausserdem etwa Urteil 6B_1074/2020 vom 3. Februar 2021 E. 6).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Das Urteil des Versicherungsgerichts des Kantons Solothurn vom 7. Januar 2021 und die Verfügung der IV-Stelle Solothurn vom 13. Mai 2020 werden aufgehoben. Die Sache wird zu weiterer Abklärung und neuer Verfügung an die IV-Stelle Solothurn zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Versicherungsgericht des Kantons Solothurn zurückgewiesen.
5.
Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 23. Juni 2021
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Parrino
Die Gerichtsschreiberin: Oswald