Sachverhalt:
A.
Die IV-Stelle des Kantons Zürich sprach dem im Dezember 1969 geborenen A._ eine halbe Invalidenrente ab dem 1. Februar 2001 resp. eine ganze Rente ab dem 1. März 2002 zu (Verfügungen vom 11. Februar 2003 resp. 11. Juni 2004; Invaliditätsgrad von 59 resp. 100 %). Am 3. August 2006 bestätigte sie einen unveränderten Anspruch und Invaliditätsgrad. Im September 2011 leitete sie erneut ein Revisionsverfahren ein. Nach Abklärungen und Durchführung des Vorbescheidverfahrens reduzierte die Verwaltung mit Verfügung vom 4. Mai 2017 die bisherige ganze auf eine halbe Invalidenrente ab dem 1. Juli 2017.
B.
Die dagegen erhobene Beschwerde wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 4. Februar 2019 ab.
C.
A._ lässt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen, der Entscheid vom 4. Februar 2019 und die Verfügung vom 4. Mai 2017 seien aufzuheben; eventualiter sei die Sache unter Aufhebung des Entscheids vom 4. Februar 2019 an die Verwaltung zurückzuweisen.
Die IV-Stelle schliesst auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

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 (Art. 106 Abs. 1 BGG). 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 (Art. 105 Abs. 1 BGG). Es kann ihre Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
2.
Ändert sich der Invaliditätsgrad eines Rentenbezügers erheblich, so wird die Rente von Amtes wegen oder auf Gesuch hin für die Zukunft entsprechend erhöht, herabgesetzt oder aufgehoben (Art. 17 Abs. 1 ATSG).
Bei einem Invaliditätsgrad von mindestens 50 % besteht Anspruch auf eine halbe Rente, während der Anspruch auf eine Dreiviertelsrente eine Invalidität von mindestens 60 % und jener auf eine ganze Rente eine solche von mindestens 70 % voraussetzt (Art. 28 Abs. 2 IVG). Für die Bestimmung des Invaliditätsgrades wird das Erwerbseinkommen, das die versicherte Person nach Eintritt der Invalidität und nach Durchführung der medizinischen Behandlung und allfälliger Eingliederungsmassnahmen durch eine ihr zumutbare Tätigkeit bei ausgeglichener Arbeitsmarktlage erzielen könnte, in Beziehung gesetzt zum Erwerbseinkommen, das sie erzielen könnte, wenn sie nicht invalid geworden wäre (Art. 16 ATSG i.V.m. Art. 28a Abs. 1 IVG). Der Einkommensvergleich 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 (Urteil 9C_63/2018 vom 9. November 2018 E. 4.4.2).
3.
Die Vorinstanz hat gestützt auf das polydisziplinäre Gutachten des BEGAZ Begutachtungszentrums BL (nachfolgend: BEGAZ) vom 8. September 2016 eine revisionsrechtlich relevante Veränderung des Sachverhalts (verbesserter Gesundheitszustand) und nunmehr eine Arbeitsfähigkeit von 60 % in angepasster Tätigkeit festgestellt. Sodann bestätigte sie die von der IV-Stelle auf der Grundlage von Tabellenlöhnen der schweizerischen Lohnstrukturerhebung (LSE) des Bundesamtes für Statistik (BfS) ermittelten Vergleichseinkommen für das Jahr 2016 (Valideneinkommen von Fr. 88'575.- und Invalideneinkommen von Fr. 40'112.-). Beim resultierenden Invaliditätsgrad von 55 % bejahte sie den Anspruch auf eine halbe Invalidenrente ab dem 1. Juli 2017.
4.
4.1. In der Beschwerde wird vorgebracht, das kantonale Gericht habe nicht nachvollziehbar begründet, weshalb es das Valideneinkommen auf der Grundlage eines LSE-Tabellenlohnes festgelegt hat. Indessen war eine sachgerechte Anfechtung des vorinstanzlichen Entscheids möglich; es kann somit nicht von einer Verletzung der Begründungspflicht resp. des Anspruchs auf rechtliches Gehör gesprochen werden (vgl. <ref-ruling> E. 4.3.2 S. 436 mit Hinweisen).
Streitig und zu prüfen ist einzig die Höhe der Vergleichseinkommen: Der Beschwerdeführer will für das Valideneinkommen am tatsächlich in den Jahren 1997 bis 1999 erzielten Lohn anknüpfen. Für das Invalideneinkommen verlangt er unter Verweis auf gesundheitliche Beeinträchtigungen, den reduzierten Beschäftigungsgrad und seine lange Abwesenheit vom Arbeitsmarkt einen Abzug vom Tabellenlohn.
4.2.
4.2.1. 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 Juli 2017) ü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). Weist das zuletzt erzielte Einkommen starke und verhältnismässig kurzfristig in Erscheinung getretene Schwankungen auf, ist auf den während einer längeren Zeitspanne erzielten Durchschnittsverdienst abzustellen (Urteile 9C_14/2019 vom 24. April 2019 E. 2.2.2; 8C_443/2018 vom 30. Januar 2019 E. 2.1 mit Hinweisen).
Die objektive Beweislast dafür, dass in einem konkreten Fall die Regel der Anknüpfung an den zuletzt erzielten Verdienst nicht greift, trifft die IV-Stelle, wenn sich ein Abweichen davon zu ihren Gunsten (niedrigeres Valideneinkommen) auswirkt (Art. 8 ZGB; Urteile 9C_38/2019 vom 9. Mai 2019 E. 3.2.2; 9C_796/2018 vom 10. Januar 2019 E. 2.1).
4.2.2. Vom anhand der LSE-Tabellenlöhne ermittelten Invalideneinkommen kann unter bestimmten Voraussetzungen ein Abzug vorgenommen werden. Damit soll der Tatsache Rechnung getragen werden, dass persönliche und berufliche Merkmale, wie Art und Ausmass der Behinderung, Lebensalter, Dienstjahre, Nationalität oder Aufenthaltskategorie und Beschäftigungsgrad Auswirkungen auf die Lohnhöhe haben können und je nach Ausprägung die versicherte Person deswegen die verbliebene Arbeitsfähigkeit auch auf einem ausgeglichenen Arbeitsmarkt nur mit unterdurchschnittlichem erwerblichem Erfolg verwerten kann. Der Einfluss aller Merkmale auf das Invalideneinkommen ist unter Würdigung der Umstände im Einzelfall nach pflichtgemässem Ermessen gesamthaft zu schätzen. Der Abzug darf 25 % nicht übersteigen (<ref-ruling> E. 5.2 S. 301; <ref-ruling> E. 5b/aa-cc S. 79 f.; SVR 2019 UV Nr. 7 S. 27, 8C_58/2018 E. 3.1.1).
4.2.3. Auf der 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 ob ein Leidensabzug vorzunehmen ist (<ref-ruling> E. 2.4 S. 297; <ref-ruling> E. 3.3 S. 399).
4.3.
4.3.1. Laut (verbindlicher; E. 1) vorinstanzlicher Feststellung arbeitete der Versicherte vor dem Eintritt des Gesundheitsschadens im Februar 2000 als Krankenpfleger bei der B._ AG. Das kantonale Gericht hat für nicht überwiegend wahrscheinlich gehalten, dass er ohne gesundheitliche Beeinträchtigung "über 18 Jahre später" seine frühere Arbeit immer noch ausüben würde. Wie die IV-Stelle in der angefochtenen Verfügung begründete es somit das Heranziehen eines Tabellenlohnes einzig mit dem Zeitablauf.
4.3.2. Zwar kommt es häufig vor, dass eine Person im Alter von rund 47 Jahren (Zeitpunkt der Invaliditätsbemessung; E. 4.2.1 in initio) nicht mehr die gleiche Tätigkeit wie im Alter von rund 30 Jahren ausübt. Indessen ist eine solche Konstellation auch nicht dermassen unwahrscheinlich, dass allein der Zeitablauf ein Abweichen von der allgemeinen Regel (E. 4.2.1) rechtfertigen würde (vgl. Urteile 9C_38/2019 vom 9. Mai 2019 E. 3.4.2; 9C_818/2018 vom 5. April 2019 E. 4.3), zumal der hier betroffene Versicherte beim Eintritt des Gesundheitsschadens kein Berufseinsteiger war (vgl. SVR 2017 IV Nr. 4 S. 7, 9C_770/2015 E. 4.4.2). Dass aus anderen Gründen nicht an die bisherige Tätigkeit angeknüpft werden dürfte, legt (e) weder die Vorinstanz noch die IV-Stelle (vgl. zur Begründungsobliegenheit der Beschwerdegegnerin Art. 42 Abs. 1 BGG; LAURENT MERZ, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 8 zu Art. 42 BGG) dar, weshalb sich diesbezügliche Weiterungen erübrigen.
4.3.3. Angesichts der im Auszug aus dem individuellen Konto ersichtlichen Einkommensschwankungen ist - entsprechend der unwidersprochen gebliebenen Argumentation des Beschwerdeführers - auf das durchschnittliche Einkommen der Jahre 1997 bis 1999 abzustellen und dieses an die allgemeine Nominallohnentwicklung zwischen 2000 und 2017 anzupassen (vgl. E. 4.2.1). Der Versicherte erzielte in den Jahren 1997 bis 1999 einen durchschnittlichen Jahreslohn von Fr. 101'535.-. Unter Berücksichtigung der Nominallohnentwicklung (BfS, Nominallohnindex 1993-2018, Tabelle T1.93, Total Männer) beträgt das hier zu berücksichtigende Valideneinkommen 2017 Fr. 122'986.-.
4.4.
4.4.1. Die Vergleichseinkommen sind auf zeitidentischer Grundlage zu erheben (<ref-ruling> E. 4.2 S. 224; <ref-ruling> E. 4a in fine S. 175). Das vorinstanzlich berücksichtigte Invalideneinkommen des Jahres 2016 von Fr. 40'112.- (E. 3) ist vorab an die Nominallohnentwicklung im Folgejahr 2017 anzupassen (vgl. E. 4.2.1 in initio). Daraus resultiert der Betrag von Fr. 40'268.-.
4.4.2. Das kantonale Gericht hat den gesundheitlichen Beeinträchtigungen des Versicherten (insbesondere eingeschränkte Leistungsfähigkeit, Verlangsamung, Pausenbedarf, somatische und kognitive Einschränkungen) in zweierlei Hinsicht Rechnung getragen: einerseits qualitativ mit der Art der zumutbaren Tätigkeiten (körperlich leichte bis intermittierend mittelschwere, wechselbelastende und rückenadaptierte Tätigkeiten ohne Zwangshaltungen, Rotationsbelastungen und Sturzgefahr; ausgeschlossen sind komplexe, emotional belastende oder mit Verantwortung verbundene Tätigkeiten) und der Berücksichtigung eines Tabellenlohnes des untersten Kompetenzniveaus; anderseits quantitativ mit der um 40 % reduzierten Arbeitsfähigkeit. Ein leidensbedingter Abzug würde somit zu einer doppelten Anrechnung derselben Gesichtspunkte führen, was nicht angeht (Urteile 8C_805/2016 vom 22. März 2017 E. 3.1; 8C_203/2019 vom 18. Juli 2019 E. 5.3).
Mit Blick auf die Art der zumutbaren Tätigkeiten wirkt sich die lange Abwesenheit vom Arbeitsmarkt nicht (zwingend) lohnsenkend aus (Urteile 9C_418/2017 vom 30. Oktober 2017 E. 4.5.2; 8C_805/2016 vom 22. März 2017 E. 3.3 und 3.4.3). Entgegen der Darstellung des Beschwerdeführers leuchtet auch nicht ein, weshalb die frühere Berufsausbildung und -ausübung (Krankenpfleger) für angepasste Arbeiten einen im Vergleich zum Mittelwert niedrigeren Lohn bewirken sollen.
Grundsätzlich ist ein Abzug vom Tabellenlohn vorzunehmen, wenn ein Versicherter seine Arbeitsfähigkeit nicht vollschichtig umsetzen kann (Urteile 9C_232/2019 vom 26. Juni 2019 E. 3.1; 9C_38/2019 vom 9. Mai 2019 E. 3.5), weil Teilzeitarbeit bei Männern statistisch gesehen vergleichsweise weniger gut entlöhnt wird als eine Vollzeittätigkeit. Allerdings muss dies stets mit Blick auf den konkreten Beschäftigungsgrad (vorliegend 60 %) und die jeweils aktuellen Werte beurteilt werden (Urteil 8C_805/2016 vom 22. März 2017 E. 3.2). In der für das Jahr 2016 aktualisierten Tabelle (LSE 2016 Tabelle T 18) beläuft sich die Differenz bei Männern auf der untersten Stufe der beruflichen Stellung (ohne Kaderfunktion) im Vergleich zu einem Vollzeitpensum auf 4,16 % und im Vergleich zum Totalwert auf 4,02 %. Es kann offenbleiben, ob der Beschwerdeführer seine Restarbeitsfähigkeit vollschichtig (mit reduzierter Leistungsfähigkeit) umsetzten könnte (worauf der im BEGAZ-Gutachten ausgewiesene Pausenbedarf deutet). Nicht näher zu prüfen ist auch, ob (allein) wegen der statistischen Lohndifferenz ein Tabellenlohnabzug angezeigt ist. Ein solcher wäre maximal mit 5 % zu veranschlagen, weshalb das Invalideneinkommen mindestens Fr. 38'255.- beträgt.
4.5. Bei einem Valideneinkommen von Fr. 122'986.- (E. 4.3.3) und einem Invalideneinkommen von Fr. 40'268.- (E. 4.4.1) resp. Fr. 38'255.- (E. 4.4.2) resultiert ein Invaliditätsgrad von 67 % resp. 69 %. Damit besteht ab dem 1. Juli 2017 Anspruch auf eine Dreiviertelsrente (E. 2). Insoweit ist die Beschwerde begründet.
5.
Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Kosten zu tragen (Art. 66 Abs. 1 BGG). Der Beschwerdeführer hat Anspruch auf eine Parteientschädigung (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 4. Februar 2019 und die Verfügung der IV-Stelle des Kantons Zürich vom 4. Mai 2017 werden aufgehoben. Die Beschwerdegegnerin hat dem Beschwerdeführer eine Dreiviertelsrente ab dem 1. Juli 2017 auszurichten. Im Übrigen wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Kosten und 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, 11. September 2019
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Pfiffner
Die Gerichtsschreiberin: Dormann