Sachverhalt:
A.
A.a. Die IV-Stelle Basel-Landschaft sprach dem 1965 geborenen A._ mit Verfügung vom 16. November 1999 eine ganze Rente der Invalidenversicherung ab 1. Februar 1999 zu (Invaliditätsgrad 100 %). Am 13. Dezember 2002 bestätigte sie einen unveränderten Anspruch. Im Frühjahr 2009 leitete die zwischenzeitlich zuständig gewordene IV-Stelle für Versicherte im Ausland (IVSTA) ein Revisionsverfahren ein, in dessen Verlauf sie u.a. Berichte der behandelnden Ärzte und das psychiatrische Gutachten des Dr. med. B._ vom 8. Juni 2010 einholte. Nach Durchführung des Vorbescheidverfahrens ermittelte sie einen Invaliditätsgrad von 50 %. Mit Verfügung vom 18. Januar 2011 setzte sie die bisherige ganze Rente auf eine halbe Rente ab dem 1. März 2011 herab.
A.b. Dagegen liess der Versicherte unter Beilage der Berichte des behandelnden Psychiaters Dr. med. C._ vom 7. Dezember 2010 und des Hausarztes Dr. med. D._ vom 12. Februar 2011 Beschwerde führen. Entsprechend dem Antrag der IVSTA wies das Bundesverwaltungsgericht die Sache zu weiterer Abklärung und neuer Verfügung an die Verwaltung zurück (Entscheid vom 31. Mai 2011). Diese holte die ergänzende Stellungnahme des Dr. med. B._ vom 3. November 2011 sowie die Meinung des Regionalen Ärztlichen Dienstes dazu ein, erliess einen Vorbescheid und bestätigte die Rentenherabsetzung auf den 1. März 2011 mit Verfügung vom 15. März 2012. Nach einem weiteren Beschwerdeverfahren (Entscheid des Bundesverwaltungsgerichts vom 16. September 2014) veranlasste die IVSTA insbesondere das interdisziplinäre Gutachten des Swiss Medical Assessement- and Business-Centers (SMAB) vom 17. Juli 2015. Nach erneuter Durchführung des Vorbescheidverfahrens bestätigte sie mit Verfügung vom 27. Juli 2016 wiederum den "weiterhin" bestehenden Anspruch auf eine halbe Invalidenrente.
B.
A._ liess auch die Verfügung vom 27. Juli 2016 anfechten. Das Bundesverwaltungsgericht hiess das Rechtsmittel mit Entscheid vom 12. Oktober 2018 insofern teilweise gut, als es die Rente erst auf den 1. September 2016 herabsetzte.
C.
C.a. Die IVSTA beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten (Verfahren 9C_818/2018), der Entscheid vom 12. Oktober 2018 sei aufzuheben, und die Verfügung vom 27. Juli 2016 sei vollumfänglich, d.h. auch im Hinblick auf den Zeitpunkt der Rentenherabsetzung, zu bestätigen. Ausserdem sei der Beschwerde die aufschiebende Wirkung zuzuerkennen.
A._ lässt auf Abweisung des Rechtsmittels schliessen. Ferner ersucht er um unentgeltliche Rechtspflege. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.
C.b. A._ lässt ebenfalls Beschwerde führen (Verfahren 9C_826/2018). Er ersucht um mindestens eine Dreiviertelsrente ab 1. September 2016 und um unentgeltliche Rechtspflege auch für dieses Verfahren.

Erwägungen:
1.
1.1. Da den beiden Beschwerden der gleiche Sachverhalt zugrunde liegt und die Rechtsmittel sich gegen den nämlichen Entscheid des Bundesverwaltungsgerichts richten, rechtfertigt es sich, die beiden Verfahren 9C_818/2018 und 9C_826/2018 zu vereinigen und in einem Urteil zu erledigen (<ref-law> [SR 273] i.V.m. <ref-law>).
1.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 S. 389). 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).
2.
Das Bundesverwaltungsgericht hat erwogen, der Gesundheitszustand des Versicherten habe sich im Vergleich zum Zustand bei der Rentenzusprache verbessert. Aus psychischer Sicht bestehe seit der 2010 erfolgten Begutachtung durch Dr. med. B._ eine Arbeitsfähigkeit von nunmehr 50 %. In somatischer Hinsicht sei die bisherige Tätigkeit als Baureiniger nicht mehr zumutbar, hingegen seien angepasste Arbeiten uneingeschränkt möglich. Die somatischen Funktionseinbussen seien erst mit dem SMAB-Gutachten rechtsgenüglich erstellt worden, weshalb die Rente nach <ref-law> (SR 831.201) nicht rückwirkend, sondern nur ex nunc et pro futuro herabgesetzt werden könne. Folglich hat die Vorinstanz die Invaliditätsbemessung resp. den Einkommensvergleich (vgl. <ref-law> i.V.m. <ref-law>) für das Jahr 2016 vorgenommen. Das Valideneinkommen hat sie auf Fr. 4'932.-, das Invalideneinkommen auf Fr. 2'305.80 festgelegt. Beim resultierenden Invaliditätsgrad von 53 % hat sie die bisherige Rente auf eine halbe Invalidenrente ab dem 1. September 2016 herabgesetzt.
3.
3.1. Von Seiten der IV-Stelle (9C_818/2018) ist einzig der Zeitpunkt der Rentenherabsetzung umstritten.
3.2. In der Invalidenversicherung erfolgt die Herabsetzung oder Aufhebung einer Rente in der Regel auf das Ende des der Zustellung der Verfügung folgenden Monats (<ref-law>). Massgeblich ist jene Verwaltungsverfügung, mit welcher die Herabsetzung oder Aufhebung erstmals verfügt wurde. Muss infolge eines Rückweisungsentscheides eine neue Verfügung erlassen werden, kann damit die ursprüngliche Rentenherabsetzung resp. -aufhebung (samt Wirkungszeitpunkt) rückwirkend bestätigt werden (<ref-ruling>; <ref-ruling>; SVR 2011 IV Nr. 33 S. 96, 8C_451/2010 E. 3 und 4.4; Urteile 9C_792/2018 vom 25. Januar 2019 E. 2.2; 9C_567/2017 vom 21. November 2017 E. 2.2.3). Vorbehalten bleibt der Fall, dass die IV-Stelle mit dem Erlass der angefochtenen (ersten) Revisionsverfügung, ohne formell hinreichende Abklärung der Revisionsvoraussetzungen, rechtsmissbräuchlich einen möglichst frühen Revisionszeitpunkt provozierte (vgl. <ref-ruling> E. 3.2 S. 372 und E. 4.3 S. 376; Urteil 9C_567/2017 vom 21. November 2017 E. 2.2.1 mit Hinweis).
3.3.
3.3.1. Aus dem Umstand allein, dass die Arbeitsfähigkeit (50 % in angepasster Tätigkeit) resp. die Unzumutbarkeit der bisherigen Tätigkeit erst mit dem SMAB-Gutachten feststand, ergibt sich nichts für den Versicherten. Die Notwendigkeit weiterer Abklärungen ist Rückweisungsentscheiden inhärent und steht der rückwirkenden Bestätigung der ursprünglichen Rentenherabsetzung nicht entgegen, wie sich aus der soeben (E. 3.2) dargelegten Praxis ergibt. Ein Grund für eine Änderung der Rechtsprechung (vgl. dazu <ref-ruling> E. 5.5.1; <ref-ruling> E. 4.5 S. 541; je mit Hinweisen) ist nicht ersichtlich und wird auch nicht geltend gemacht.
3.3.2. Die Rückweisungen vom 31. Mai 2011 und 16. September 2014 erfolgten nicht aus formellen, sondern aus materiellen Gründen. Im ersten Beschwerdeverfahren war einzig der psychische Gesundheitszustand und in diesem Zusammenhang die Beweiskraft der Expertise des Dr. med. B._ vom 8. Juni 2010 umstritten. Diesbezüglich erkannte das Bundesverwaltungsgericht - wie die IVSTA - Abklärungsbedarf aufgrund zweier Berichte behandelnder Ärzte, die erst mit der Beschwerde vom 22. Februar 2011 aktenkundig geworden waren (vgl. Sachverhalt lit. A.b). Im zweiten Beschwerdeverfahren kam das Gericht zum Schluss, dass die psychiatrischen Unterlagen inhaltlich nicht überzeugten; zudem hielt es - ohne dass dies vom anwaltlich vertretenen Versicherten je auch nur ansatzweise thematisiert worden war - somatische Abklärungen für erforderlich. Bei diesen Gegebenheiten kann nicht angenommen werden, dass mit dem Erlass der Verfügung vom 18. Januar 2011 rechtsmissbräuchlich ein möglichst früher Revisionszeitpunkt provoziert werden sollte. Solches legt denn auch weder die Vorinstanz noch der Versicherte dar.
3.4. Nach dem Gesagten hat das Bundesverwaltungsgericht Recht verletzt, indem es die Rückwirkung der Rentenherabsetzung auf den 1. März 2011 für unzulässig gehalten hat. Die Beschwerde der IV-Stelle ist begründet. Vorbehalten bleibt das Ergebnis der Prüfung des Rentenanspruchs an sich (dazu sogleich E. 4).
4.
4.1. Der Versicherte (9C_826/2018) rügt lediglich die Festsetzung des Valideneinkommens. Die Vorinstanz habe dafür gestützt auf einen Auszug aus dem Individuellen Konto (IK) an einen 1997 als Baureiniger (möglicherweise) erzielten Lohn angeknüpft. Richtigerweise sei der Tabellenlohn der Lohnstrukturerhebung des Bundesamtes für Statistik (LSE) 2014, T17, Position 93 (Hilfskräfte Bau), für Männer heranzuziehen, was 2016 (unter Berücksichtigung der betriebsüblichen Wochenarbeitszeit und der Nominallohnentwicklung) ein Valideneinkommen von Fr. 6'253.44 ergebe. Beim resultierenden Invaliditätsgrad von 63 % bestehe Anspruch auf eine Dreiviertelsrente. Die Anwendung des Tabellenlohnes gemäss T17 der LSE ermögliche es besser als die Aufindexierung des Lohnes seit 1997, den konkreten Umständen (Art der Tätigkeit, Alter) Rechnung zu tragen.
4.2.
4.2.1. Der Einkommensvergleich (<ref-law>) hat in der Regel in der Weise zu erfolgen, dass die beiden hypothetischen Erwerbseinkommen ziffernmässig möglichst genau ermittelt und einander gegenübergestellt werden, worauf sich aus der Einkommensdifferenz der Invaliditätsgrad bestimmen lässt.
Für die Ermittlung des Valideneinkommens ist entscheidend, was der Versicherte im Zeitpunkt der Invaliditätsbemessung (hier: Anpassung des Anspruchs [vgl. SVR 2017 IV Nr. 4 S. 7, 9C_770/2015 E. 4.2.2], mithin März 2011) überwiegend wahrscheinlich als Gesunder tatsächlich verdient hätte. Dabei wird in der Regel am zuletzt erzielten, nötigenfalls der Teuerung und der realen Einkommensentwicklung angepassten Verdienst angeknüpft, da es der Erfahrung entspricht, dass die bisherige Tätigkeit ohne Gesundheitsschaden fortgesetzt worden wäre. Ausnahmen müssen mit überwiegender Wahrscheinlichkeit erstellt sein (<ref-ruling> E. 3.3.2 S. 30; <ref-ruling> E. 4.1 S. 325; SVR 2009 IV Nr. 28 S. 79, 8C_576/2008 E. 6.2; Urteil 9C_63/2018 vom 9. November 2018 E. 4.4.2).
Die Beweislast dafür, dass in einem konkreten Fall die Regel der Anknüpfung an den zuletzt erzielten Verdienst nicht greift, trifft die versicherte Person, wenn sich ein Abweichen davon zu ihren Gunsten (höheres Valideneinkommen) auswirkt (<ref-law>; Urteil 9C_796/2018 vom 10. Januar 2019 E. 2.1).
4.2.2. Auf der nicht medizinischen beruflich-erwerblichen Stufe der Invaliditätsbemessung charakterisieren sich als Rechtsfragen die gesetzlichen und rechtsprechungsgemässen Regeln über die Durchführung des Einkommensvergleichs, einschliesslich derjenigen über die Anwendung der LSE. In dieser Sicht ist die Feststellung der beiden hypothetischen Vergleichseinkommen Tatfrage, soweit sie auf konkreter Beweiswürdigung beruht, hingegen Rechtsfrage, soweit sich der Entscheid nach der allgemeinen Lebenserfahrung richtet. Letzteres betrifft etwa die Fragen, ob Tabellenlöhne anwendbar sind und welches die massgebende Tabelle ist (<ref-ruling> E. 3.3 S. 399; Urteil 9C_217/2017 vom 21. Dezember 2017 E. 1.2).
4.3. Dass für das Valideneinkommen an die angestammte Tätigkeit angeknüpft und für das Invalideneinkommen - insbesondere wenn die Restarbeitsfähigkeit nicht ausgeschöpft wird (vgl. <ref-ruling> E. 4.2.1 S. 475 mit Hinweisen) - auf einen Tabellenlohn abgestellt wird, entspricht gängiger Praxis. Die Vorinstanz hat verbindlich (E. 1.2) festgestellt, dass der Versicherte bis zum Eintritt der Arbeitsunfähigkeit am 23. Februar 1998 als Baureiniger gearbeitet habe. Der Beschwerdeführer will das Valideneinkommen auf der Grundlage dieser Tätigkeit festlegen, was das Bundesverwaltungsgericht denn auch getan hat. Ein klarer Anhaltspunkt dafür, dass der Versicherte 2011 (vgl. E. 4.2.1), d.h. 13 Jahre nach Eintritt der Arbeitsunfähigkeit, bei uneingeschränkter Arbeitsfähigkeit nicht mehr bei seiner früheren Arbeitgeberin tätig gewesen wäre, ist nicht ersichtlich und wird auch nicht substanziiert geltend gemacht. Ebenso fehlt es an eindeutigen Hinweisen dafür, dass das von der Vorinstanz als Ausgangsgrösse berücksichtigte Einkommen des Jahres 1997 gemäss IK-Auszug unzutreffend sein sollte; insbesondere ist es höher als der im Arbeitgeberbericht vom 4. Mai 1999 für das Jahr 1998 angegebene Verdienst. Weshalb die konkreten Umstände in einem Tabellenlohn besser abgebildet sein sollen als im tatsächlich erzielten (und der allgemeinen Lohnentwicklung angepassten) Einkommen, leuchtet nicht ein. Demnach stellt es keine Rechtsverletzung dar, dass die Vorinstanz für die Festlegung des Valideneinkommens nicht einen Tabellenwert herangezogen hat.
4.4. Das Bundesverwaltungsgericht hat die Vergleichseinkommen zwar für das Jahr 2016, aber auf zeitidentischer Grundlage erhoben (vgl. <ref-ruling> E. 4.2 S. 224; <ref-ruling> E. 4a in fine S. 175; vgl. auch Urteil 9C_479/2015 vom 22. Dezember 2015 E. 4.1). Es besteht somit kein Anlass für eine nähere Prüfung der Invaliditätsbemessung von Amtes wegen (E. 1.2). Die Beschwerde des Versicherten ist unbegründet.
5.
Mit diesem Urteil wird das Gesuch der IVSTA um aufschiebende Wirkung der Beschwerde gegenstandslos.
6.
Dem Ausgang des Verfahrens entsprechend hat der Versicherte grundsätzlich die Gerichtskosten zu tragen (<ref-law>). Seinen Gesuchen um unentgeltliche Rechtspflege kann jedoch entsprochen werden (<ref-law>). Er hat der Bundesgerichtskasse Ersatz zu leisten, wenn er später dazu in der Lage ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 9C_818/2018 und 9C_826/2018 werden vereinigt.
2.
Die Beschwerde im Verfahren 9C_818/2018 wird gutgeheissen. Der Entscheid des Bundesverwaltungsgerichts vom 12. Oktober 2018 wird aufgehoben und die Verfügung der IV-Stelle für Versicherte im Ausland IVSTA vom 27. Juli 2016 wird bestätigt.
3.
Die Beschwerde im Verfahren 9C_826/2018 wird abgewiesen.
4.
Dem Versicherten wird die unentgeltliche Rechtspflege gewährt und Advokat Jürg Tschopp wird als unentgeltlicher Anwalt bestellt.
5.
Die Gerichtskosten von insgesamt Fr. 1'600.- werden dem Versicherten auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
6.
Dem Rechtsvertreter des Versicherten wird aus der Bundesgerichtskasse eine Entschädigung von insgesamt Fr. 5'200.- ausgerichtet.
7.
Die Sache wird zur Neuverlegung der Kosten des vorangegangenen Verfahrens an das Bundesverwaltungsgericht zurückgewiesen.
8.
Dieses Urteil wird den Parteien, dem Bundesverwaltungsgericht, Abteilung III, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 5. April 2019
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Pfiffner
Die Gerichtsschreiberin: Dormann