Sachverhalt:
A.
Der 1957 geborene A._ bezog eine ganze Invalidenrente seit dem 1. August 2000 (Invaliditätsgrad 75 %; Verfügung vom 20. September 2000, bestätigt am 14. November 2002 und 20. Mai 2005). Im August 2011 leitete die IV-Stelle Solothurn (erneut) ein Revisionsverfahren ein. In dessen Verlauf kam es zu verschiedenen Verzögerungen, insbesondere zu Beschwerdeverfahren betreffend eine medizinische Begutachtung (beendet mit Urteil des Versicherungsgerichts des Kantons Solothurn vom 23. März 2016 resp. Urteil 9C_294/2016 des Bundesgerichts vom 27. Mai 2016). Nach Abklärungen und Durchführung des Vorbescheidverfahrens ermittelte die IV-Stelle einen Invaliditätsgrad von 40 %. Mit Verfügung vom 26. Januar 2018 reduzierte sie die bisherige ganze Invalidenrente auf Ende Februar 2018 auf eine Viertelsrente. Dementsprechend legte sie mit Verfügung vom 1. Februar 2018 den Rentenanspruch des A._ ab dem 1. März 2018 fest.
B.
Das Versicherungsgericht des Kantons Solothurn hiess die Beschwerde des A._ mit Urteil vom 21. Dezember 2020 gut und hob die Verfügungen vom 26. Januar und 1. Februar 2018 auf.
C.
Die IV-Stelle beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, das Urteil vom 21. Dezember 2020 sei aufzuheben und ihre Verfügungen vom 26. Januar und 1. Februar 2018 seien zu bestätigen. Ferner ersucht sie um aufschiebende Wirkung der Beschwerde.
A._ lässt beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei; eventualiter sei die Sache zwecks weiterer Abklärungen an das kantonale Gericht zurückzuweisen. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung. Die IV-Stelle und A._ reichen je eine weitere Eingabe ein.

Erwägungen:
1.
1.1. Das Bundesgericht prüft seine Zuständigkeit und die (weiteren) Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1 mit Hinweis).
1.2. Die Vorinstanz hat die Voraussetzungen für eine Wiedererwägung (vgl. <ref-law>) der rentenzusprechenden Verfügung vom 20. September 2000 bejaht und eine Arbeitsfähigkeit von 75 % in angepasster Tätigkeit festgestellt. Indessen hat sie deren Verwertbarkeit auf dem Weg der Selbsteingliederung verneint. In diesem Zusammenhang hat sie auf die grundsätzliche Unzumutbarkeit der Selbsteingliederung bei fortgeschrittenem Alter sowie langjährigem Rentenbezug verwiesen und festgestellt, in der konkreten Konstellation lasse sich die subjektive Eingliederungsfähigkeit des Versicherten nicht verneinen. Folglich sei es unzulässig gewesen, seine Rente herabzusetzen, ohne ihm zuvor Eingliederungsmassnahmen angeboten zu haben.
Mit der vorinstanzlichen Aufhebung der angefochtenen Verfügungen bleibt es beim bisherigen Anspruch auf eine ganze Invalidenrente. Das kantonale Gericht hat somit über den umstrittenen Rentenanspruch ab dem 1. März 2018 abschliessend entschieden. Anders als die Beschwerdeführerin anzunehmen scheint, handelt es sich beim angefochtenen Urteil auch nicht sinngemäss um einen Zwischenentscheid gemäss <ref-law>. Vielmehr liegt ein Endentscheid im Sinne von <ref-law> vor (vgl. Urteil 9C_396/2019 vom 2. März 2020 E. 2.2 mit Hinweis auf JOHANNA DORMANN, Aufschiebende Wirkung des Rechtsmittels in sozialversicherungsrechtlichen Verfahren, SZS 2019 S. 257).
1.3. Die Eingaben der IV-Stelle im vorinstanzlichen wie auch in diesem Verfahren wurden von einem juristischen Mitarbeiter des Rechtsdienstes der IV-Stelle unterzeichnet. Der Beschwerdegegner bestreitet dessen Vertretungsbefugnis. Abgesehen davon, dass er diese Rüge erstmals in diesem Verfahren vorbringt (vgl. <ref-ruling> E. 4.3), hält sie nicht stand: Die Vertretungsbefugnis ergibt sich aus Ziff. 3.3.2 und 5.7 des von der Beschwerdeführerin mit der Replik eingereichten Geschäftsreglements über Organisation, Aufgaben und Zuständigkeiten der IV-Stelle Solothurn. Dieses ist im Lichte von <ref-law> zulässig (vgl. Urteile 5A_448/2020 vom 18. Februar 2021 E. 2.4.4; 5A_241/2017 vom 18. Juli 2017 E. 1.1; vgl. auch JOHANNA DORMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 34a zu <ref-law>), und der Beschwerdegegner bringt gegen dessen Massgeblichkeit nichts vor. Somit ist auch unter diesem Aspekt auf die Beschwerde einzutreten.
2.
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 f. BGG; <ref-ruling> E. 2.2.1). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es 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, Art. 105 Abs. 2 BGG).
Eine Sachverhaltsfeststellung ist nicht schon dann offensichtlich unrichtig, wenn sich Zweifel anmelden, sondern erst, wenn sie eindeutig und augenfällig unzutreffend ist. Eine offensichtlich unrichtige Sachverhaltsfeststellung weist damit die Tragweite von Willkür auf. Es liegt noch keine offensichtliche Unrichtigkeit vor, nur weil eine andere Lösung ebenfalls in Betracht fällt, selbst wenn diese als die plausiblere erscheint. Eine Sachverhaltsfeststellung ist etwa dann offensichtlich unrichtig, wenn das kantonale Gericht den Sinn und die Tragweite eines Beweismittels offensichtlich falsch eingeschätzt, ohne sachlichen Grund ein wichtiges und für den Ausgang des Verfahrens entscheidendes Beweismittel nicht beachtet oder aus den abgenommenen Beweisen unhaltbare Schlüsse gezogen hat. Solche Mängel sind in der Beschwerde aufgrund des strengen Rügeprinzips (vgl. <ref-law>) klar und detailliert aufzuzeigen (<ref-ruling> E. 4.2 mit Hinweisen; Urteil 9C_752/2018 vom 12. April 2019 E. 1.2).
3.
3.1. Streitig und zu prüfen ist einzig, ob das kantonale Gericht zu Recht die Rentenherabsetzung von vorgängigen Eingliederungsmassnahmen abhängig gemacht hat.
3.2.
3.2.1. Bei Personen, deren Rente revisions- resp. wiedererwägungsweise herabgesetzt oder aufgehoben werden soll, sind nach mindestens fünfzehn Jahren Bezugsdauer oder wenn sie das 55. Altersjahr zurückgelegt haben, praxisgemäss in der Regel vorgängig Massnahmen zur Eingliederung durchzuführen, bis sie in der Lage sind, das medizinisch-theoretisch (wieder) ausgewiesene Leistungspotenzial mittels Eigenanstrengung auszuschöpfen und erwerblich zu verwerten. Ausnahmen von der diesfalls grundsätzlich ("vermutungsweise") anzunehmenden Unzumutbarkeit einer Selbsteingliederung liegen namentlich dann vor, wenn die langjährige Absenz vom Arbeitsmarkt auf invaliditätsfremde Gründe zurückzuführen ist (etwa bei einer stets vorhandenen, aber nicht verwerteten Restarbeitsfähigkeit; vgl. <ref-ruling> E. 5.3 S. 393 in fine mit Hinweisen), wenn die versicherte Person besonders agil, gewandt und im gesellschaftlichen Leben integriert ist, oder wenn sie über besonders breite Ausbildungen und Berufserfahrungen verfügt. Verlangt sind immer konkrete Anhaltspunkte, die den Schluss zulassen, die versicherte Person könne sich trotz ihres fortgeschrittenen Alters und/oder der langen Rentenbezugsdauer mit entsprechender Absenz vom Arbeitsmarkt ohne Hilfestellungen wieder in das Erwerbsleben integrieren (<ref-ruling> E. 5.1 mit zahlreichen Hinweisen; Urteil 9C_541/2020 vom 1. März 2021 E. 4.4.2).
3.2.2. Fehlt der Eingliederungswille bzw. die subjektive Eingliederungsfähigkeit, d.h. ist die Eingliederungsbereitschaft aus invaliditätsfremden Gründen nicht gegeben, darf die Rente ohne vorgängige Prüfung von Massnahmen der (Wieder-) Eingliederung und ohne Durchführung des Mahn- und Bedenkzeitverfahrens nach <ref-law> herabgesetzt oder aufgehoben werden. Berufliche Massnahmen können zwar unter anderem dazu dienen, subjektive Eingliederungshindernisse im Sinne einer Krankheitsüberzeugung der versicherten Person zu beseitigen. Es bedarf indessen auch diesfalls eines Eingliederungswillens bzw. einer entsprechenden Motivation der versicherten Person. Es sind insbesondere die gegenüber der Verwaltung und den medizinischen Experten gemachten Aussagen betreffend Krankheitsüberzeugung bzw. Arbeitsmotivation zu berücksichtigen. Ebenfalls von Belang sein können die im Vorbescheidverfahren und vor dem kantonalen Versicherungsgericht gemachten Ausführungen resp. gestellten Anträge (Urteile 9C_541/2020 vom 1. März 2021 E. 4.4.2; 9C_50/2020 vom 9. Juli 2020 E. 3.1; 9C_797/2018 vom 10. September 2019 E. 5.1).
4.
4.1. Die Vorinstanz hat u.a. festgestellt, zum Zeitpunkt der angefochtenen Verfügung sei der Versicherte 60,5 Jahre alt gewesen und habe er seit über 17 Jahren eine ganze Invalidenrente bezogen (mit entsprechend langer Abwesenheit vom Arbeitsmarkt). Er sei nicht besonders agil, gewandt und im gesellschaftlichen Leben integriert, und er verfüge auch nicht über besonders breite Ausbildungen und Berufserfahrungen. Angesichts der zugesprochenen ganzen Invalidenrente sei seinerzeit auch eine nahezu vollständige Arbeitsunfähigkeit anerkannt worden.
Soweit die IV-Stelle diese Feststellungen kritisiert, geschieht es lediglich in appellatorischer Weise. Dass sie offensichtlich unrichtig sein oder auf einer Rechtsverletzung beruhen sollen, ist nicht ersichtlich und wird auch nicht substanziiert geltend gemacht. Die vorinstanzlichen Feststellungen bleiben daher für das Bundesgericht verbindlich (vgl. vorangehende E. 2).
4.2. Auf dieser tatsächlichen Grundlage hat das kantonale Gericht die Selbsteingliederung des Versicherten für unzumutbar gehalten. Was die IV-Stelle dagegen vorbringt, hält nicht stand, wie sich aus dem Folgenden ergibt.
Zwar war in der Verfügung vom 20. September 2000 ein Invalideneinkommen von Fr. 17'160.- und ein Invaliditätsgrad von 75 % angenommen worden. Darauf kann indessen nicht abgestellt werden, nachdem die Vorinstanz - unangefochten - die genannte Verfügung als zweifellos unrichtig (infolge Verletzung des Untersuchungsgrundsatzes) qualifiziert hat. Im gleichen Zusammenhang beruft sich die Beschwerdeführerin e contrario auf E. 5.3 des Urteils 9C_446/2012 vom 16. November 2012. Die im genannten (Revisions-) Fall betroffene Versicherte war aufgrund ihrer cerebralen Einschränkung in der freien Marktwirtschaft als nicht arbeitsfähig anzusehen. Das Bundesgericht erkannte daher die (damalige) vorinstanzliche Einschätzung, bei einer vollzeitlichen Erwerbstätigkeit könnte die Betroffene monatlich rund Fr. 1000.- verdienen, als nicht realistisch. Daraus lässt sich für den hier zu beurteilenden Fall (auch e contrario) nichts ableiten. Was sodann den bestrittenen "Status als Vollinvalider" anbelangt, so legt die IV-Stelle nicht substanziiert dar, warum und in welchem Pensum der Versicherte während des langjährigen Bezugs der ganzen Invalidenrente gehalten gewesen sein soll, eine allfällige Restarbeitsfähigkeit zu verwerten. Abgesehen davon, dass in concreto eine verbindliche Feststellung betreffend die Arbeitsfähigkeit für die Zeit vor Erlass der Verfügung vom 26. Januar 2018 fehlt, bejahte das Bundesgericht eine über längere Zeit aus invaliditätsfremden Gründen nicht verwertete Restarbeitsfähigkeit (und damit eine Ausnahme von der Unzumutbarkeit einer Selbsteingliederung) denn auch regelmässig im Zusammenhang mit dem Bezug einer Teilrente (vgl. z.B. Urteile 9C_516/2020 vom 29. Dezember 2020; 9C_162/2020 vom 16. September 2020; 9C_105/2019 vom 18. Juni 2019; 8C_1/2018 vom 16. August 2018; 8C_394/2017 vom 8. August 2017; 8C_393/2016 vom 25. August 2016). Weiter leuchtet mit Blick auf die hier massgebliche Rechtsprechung (vorangehende E. 3.2.1) und auf die in <ref-law> vorgesehenen Massnahmen zur Wiedereingliederung eines Rentners nicht ein, weshalb in concreto von vornherein "maximal eine Hilfestellung in Form einer Arbeitsvermittlung nötig erscheinen" soll.
4.3. Was die subjektive Eingliederungsfähigkeit (vgl. vorangehende E. 1.2 und 3.2.2) anbelangt, so hat die Vorinstanz insbesondere folgende Aspekte berücksichtigt: die (teilweise den Behörden zuzurechnende) Verfahrensverzögerung und in diesem Zusammenhang das obstruktive Vorgehen des Versicherten bis zum Erlass des Urteils 9C_294/2016 vom 27. Mai 2016 (vgl. dessen E. 2), das Ausstandsgesuch vom 29. September 2016 (das rund drei Wochen später abgewiesen wurde), der Verlauf des zur Besprechung beruflicher Massnahmen angesetzten Gesprächs vom 19. Oktober 2017, die dabei unterzeichnete Erklärung der Bereitschaft zur Mitwirkung an beruflichen Massnahmen, das (als in höchstem Masse unprofessionell qualifizierte) Verhalten des Rechtsvertreters beim erwähnten Gespräch und dessen Bedeutung für die Beurteilung der persönlichen Einstellung des vertretenen Versicherten, die über Jahre hinweg erfolgten (wenn auch zu einem grossen Teil unrealistischen) Stellenbewerbungen mit nicht unerheblichem Aufwand und schliesslich die vom Beschwerdegegner gegenüber medizinischen Gutachtern geäusserten und mit invaliditätsfremden Umständen (Alter, Stellenmarkt) begründeten Zweifel an seiner Eingliederungsfähigkeit. Nach eingehender Würdigung und Abwägung all dieser Faktoren ist das kantonale Gericht zum Schluss gekommen, dass der Eingliederungswille nicht verneint werden könne.
4.4. Die Beschwerdeführerin bezeichnet diesen Schluss zwar als willkürlich. Inwiefern er eindeutig und augenfällig unhaltbar sein soll (vgl. vorangehende E. 2), legt sie indessen nicht schlüssig dar. Bis zum Gespräch vom 19. Oktober 2017 gab ihr denn auch das frühere Verhalten des Beschwerdegegners resp. dessen Rechtsvertreters keinen Anlass, die Eingliederungsbereitschaft in Frage zu stellen. Dass aus der Beratung resp. Verbeiständung durch einen Rechtsanwalt (vgl. dazu <ref-law>) eine Verletzung des Gleichheitssatzes von <ref-law> resultieren soll, erschliesst sich nicht und wird auch nicht substanziiert begründet (vgl. <ref-law>). Dass der Versicherte anlässlich der Untersuchung durch einen von ihm beauftragten Privatgutachter keinen albanischen Dolmetscher akzeptierte, disqualifiziert ihn nicht für Eingliederungsmassnahmen. Soweit die IV-Stelle das Verhalten des Rechtsvertreters beim Gespräch vom 19. Oktober 2017 moniert, legt sie nicht dar, weshalb es - entgegen der vorinstanzlichen Auffassung - auf fehlenden Eingliederungswillen beim Versicherten schliessen lassen soll. Sodann steht der Umstand, dass eine versicherte Person mehrfach durch inkongruentes und unkooperatives Verhalten aufgefallen ist, der Annahme der subjektiven Eingliederungsfähigkeit nicht per se entgegen (vgl. das vom kantonalen Gericht zitierte Urteil 9C_556/2015 vom 3. November 2015 E. 4.2.2). Im Übrigen beschränkt sich die IV-Stelle im hier interessierenden Kontext darauf, dem Versicherten ein stets rein prozesstaktisches Vorgehen vorzuwerfen und die von der Vorinstanz berücksichtigten Aspekte abweichend von dieser zu gewichten. Darauf ist nicht weiter einzugehen.
Demzufolge bleibt auch die vorinstanzliche Feststellung betreffend die subjektive Eingliederungsfähigkeit für das Bundesgericht verbindlich (vgl. vorangehende E. 2).
4.5. Nach dem Gesagten hat die Vorinstanz kein Recht verletzt, indem sie die Rentenherabsetzung von vorgängigen Eingliederungsmassnahmen abhängig gemacht hat. Die Beschwerde ist unbegründet.
5.
Mit diesem Urteil wird das Gesuch der Beschwerdeführerin um aufschiebende Wirkung gegenstandslos.
6.
Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten der Beschwerdeführerin aufzuerlegen (<ref-law>). Der obsiegende Beschwerdegegner hat Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 2. August 2021
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Parrino
Die Gerichtsschreiberin: Dormann