Sachverhalt:
A.
Dem 1954 geborenen A._ wurde von seinem Hausarzt unter Verweis auf eine "nervös-agitierte depressive Entwicklung" und eine "persistierende Lumboischialgie" eine vollständige Arbeitsunfähigkeit ab 3. März 2003 attestiert; im November 2003 erlitt der Versicherte einen Auffahrunfall. Im August 2004 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Basel-Landschaft ermittelte zunächst - u.a. gestützt auf das Gutachten des Zentrums für medizinische Begutachtung (ZMB) vom 23. Dezember 2005 (samt ergänzenden Stellungnahmen vom 6. November 2006 und 3. Juni 2008) - einen Invaliditätsgrad von 21 resp. 23 % und verneinte einen Rentenanspruch (Verfügung vom 15. März 2006; Einspracheentscheid vom 19. März 2010). Das Kantonsgericht Basel-Landschaft hob mit Entscheid vom 17. Februar 2011 den Einspracheentscheid vom 19. März 2010 auf und wies die Angelegenheit zur weiteren Abklärung und erneuten Verfügung an die Verwaltung zurück. Nach Einholung insbesondere des ZMB-Gutachtens vom 22. März 2012 (samt ergänzenden Stellungnahmen vom 28. Juni 2012 sowie 23. August und 29. Oktober 2013) und Durchführung des Vorbescheidverfahrens ermittelte die IV-Stelle einen Invaliditätsgrad von zunächst 14 % und ab März 2006 von 65 %. Folglich sprach sie A._ mit Verfügungen vom 23. Juli und 22. August 2014 eine Dreiviertelsrente ab 1. Juni 2006 zu.
B.
Die dagegen erhobene Beschwerde wies das Kantonsgericht Basel-Landschaft mit Entscheid vom 7. Mai 2015 (zugestellt am 3. September 2015) ab.
C.
A._ lässt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen, unter Aufhebung des Entscheids vom 7. Mai 2015 sei ihm vom 1. März 2004 bis 30. September 2004 eine ganze Invalidenrente und anschliessend eine Dreiviertelsrente auszurichten; eventualiter sei die Sache zur weiteren Abklärung an das kantonale Gericht zurückzuweisen. Die nicht bereits mit den angefochtenen Verfügungen zugesprochenen Ansprüche seien ab 1. März 2006 mit 5 % p.a. zu verzinsen. Ferner ersucht er um unentgeltliche Rechtspflege.

Erwägungen:
1.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Es wendet das Recht von Amtes wegen an (<ref-law>). Folglich ist das Bundesgericht weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.2 S. 252 mit Hinweisen).
2.
Die Vorinstanz hat gestützt auf das polydisziplinäre Gutachten des Zentrums für medizinische Begutachtung (ZMB) vom 22. März 2012festgestellt, dass der Versicherte in einer leidensadaptierten Tätigkeit vom März 2004 (Ablauf des Wartejahres) bis März 2006 uneingeschränkt und spätestens ab 2008 noch zu 50 % arbeitsfähig gewesen sei. In Abweichung vom ZMB-Gutachten ergebe sich - zu Gunsten des Versicherten - aus den Berichten über zwei halbjährige Arbeitstrainings, dass die Arbeitsfähigkeit bereits ab März 2006 um 50 % eingeschränkt gewesen sei. Weiter hat das kantonale Gericht die Invaliditätsbemessungen der IV-Stelle und folglich, unter Berücksichtigung von <ref-law> (SR 831.201), den Anspruch auf eine Dreiviertelsrente ab 1. Juni 2006 bestätigt.
Streitig und zu prüfen ist - entsprechend dem Rechtsbegehren und der Beschwerdebegründung - lediglich der Rentenanspruch vom 1. März 2004 bis zum 31. Mai 2006.
3.
3.1.
3.1.1. Bei der Beurteilung der Arbeits (un) fähigkeit stützt sich die Verwaltung und im Beschwerdefall das Gericht auf Unterlagen, die von ärztlichen und gegebenenfalls auch anderen Fachleuten zur Verfügung zu stellen sind. Ärztliche Aufgabe ist es, den Gesundheitszustand zu beurteilen und dazu Stellung zu nehmen, in welchem Umfang und bezüglich welcher Tätigkeiten die versicherte Person arbeitsunfähig ist. Hinsichtlich des Beweiswertes eines Arztberichtes ist entscheidend, ob dieser für die streitigen Belange umfassend ist, auf allseitigen Untersuchungen beruht, auch die geklagten Beschwerden berücksichtigt, in Kenntnis der Vorakten (Anamnese) abgegeben worden ist, in der Beurteilung der medizinischen Zusammenhänge sowie der medizinischen Situation einleuchtet und ob die Schlussfolgerungen der Experten begründet sind (<ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3a S. 352 mit Hinweis).
3.1.2. Der Sozialversicherungsprozess ist vom Untersuchungsgrundsatz beherrscht. Danach hat das Gericht von Amtes wegen für die richtige und vollständige Feststellung des rechtserheblichen Sachverhaltes zu sorgen. Die Verwaltung als verfügende Instanz und - im Beschwerdefall - das Gericht dürfen eine Tatsache nur dann als bewiesen annehmen, wenn sie von ihrem Bestehen überzeugt sind. Im Sozialversicherungsrecht hat das Gericht seinen Entscheid, sofern das Gesetz nicht etwas Abweichendes vorsieht, nach dem Beweisgrad der überwiegenden Wahrscheinlichkeit zu fällen. Die blosse Möglichkeit eines bestimmten Sachverhalts genügt den Beweisanforderungen nicht. Der Richter und die Richterin haben vielmehr jener Sachverhaltsdarstellung zu folgen, die sie von allen möglichen Geschehensabläufen als die wahrscheinlichste würdigen (<ref-ruling> E. 5b S. 360; <ref-ruling> E. 2 S. 195; je mit Hinweisen; vgl. <ref-ruling> E. 3.2 und 3.3 S. 324 f.; SVR 2011 UV Nr. 11 S. 39, 8C_693/2010 E. 10).
Der Untersuchungsgrundsatz schliesst die Beweislast im Sinne der Beweisführungslast begriffsnotwendig aus, da es Sache des Sozialversicherungsgerichts (oder der verfügenden Verwaltungsstelle) ist, für die Zusammentragung des Beweismaterials besorgt zu sein. Im Sozialversicherungsprozess tragen mithin die Parteien in der Regel eine Beweislast nur insofern, als im Falle der Beweislosigkeit der Entscheid zu Ungunsten jener Partei ausfällt, die aus dem unbewiesen gebliebenen Sachverhalt Rechte ableiten wollte. Diese Beweisregel greift allerdings erst Platz, wenn es sich als unmöglich erweist, im Rahmen des Untersuchungsgrundsatzes aufgrund einer Beweiswürdigung einen Sachverhalt zu ermitteln, der zumindest die Wahrscheinlichkeit für sich hat, der Wirklichkeit zu entsprechen (<ref-ruling> E. 6 S. 221 f.).
3.2. Es steht fest, dass dem Versicherten aus somatischer Sicht die bisherige Tätigkeit als Maurer nicht mehr zumutbar ist. Eine quantitative Einschränkung bei leidensangepassten Arbeiten wurde psychiatrisch begründet. Der Beschwerdeführer macht im Wesentlichen geltend, die anerkannte Arbeitsunfähigkeit von 50 % (in angepassten Tätigkeiten) sei nicht erst im März 2006 eingetreten, sondern habe bereits zuvor bestanden. Er beruft sich dabei insbesondere auf die Einschätzungen der Ärzte der Rehaklinik B._ (Austrittsbericht vom 8. Juni 2004 samt Anhang), des Hausarztes (Bericht vom 28. August 2003), des SUVA-Kreisarztes (Berichte vom 18. März und 3. August 2004) und des Neurologen Dr. med. C._ (Bericht vom 12. Februar 2005). Die ZMB-Gutachten hält er in Bezug auf die Periode bis März 2006 für nicht "beweistauglich".
3.3.
3.3.1. Aus den genannten Berichten des Hausarztes, des SUVA-Kreisarztes und des Dr. med. C._ lässt sich nichts für den Versicherten ableiten: Einerseits fehlt es für die Annahme einer anhaltenden Einschränkung der Arbeitsfähigkeit aus psychiatrischer Sicht bereits an der fachärztlichen Qualifikation (<ref-ruling> E. 5.3 und 6 S. 398 ff.). Anderseits stellte der SUVA-Kreisarzt eine Aggravation fest, während die Berichte der beiden anderen Ärzte von vornherein keine nachvollziehbare Begründung enthalten.
3.3.2. Im Austrittsbericht der Rehaklinik B._ vom 28. August 2003wurde eine um 50 % reduzierte Arbeitsfähigkeit (ganztags reduzierte Leistung) attestiert. Die unterzeichnenden Ärztinnen, die ebenfalls nicht über eine psychiatrische Fachausbildung verfügen, hatten zuvor ein fachärztliches Konsilium eingeholt. Dabei wurde wohl eine Anpassungsstörung, Angst und depressive Reaktion gemischt (ICD-10: F43.2) diagnostiziert, aber eine darauf beruhende Einschränkung der Arbeitsfähigkeit weder attestiert noch einleuchtend dargelegt. In medizinischer Hinsicht wurde denn auch lediglich die "Weiterbetreuung in der hausärztlichen Praxis" empfohlen.
3.3.3. Das kantonale Gericht stellte bei der Begründung der Rückweisung in E. 4.3 des Entscheids vom 17. Februar 2011 folgende Punkte in den Vordergrund: Der psychiatrische ZMB-Experte habe anlässlich der im Dezember 2005 erfolgten Untersuchung keine Rücksprache mit dem behandelnden Psychiater des Versicherten, Dr. med. D._, genommen und von diesem auch keinen Bericht angefordert. Sodann hätten die Gutachter, als sie ihre nachträglichen Stellungnahmen vom 6. November 2006 und 3. Juni 2008 abgaben, keine Kenntnis von den Berichten der Integrationsorganisationen über zwei absolvierte halbjährige Arbeitstrainings gehabt und sich dazu nicht geäussert. Schliesslich seien seit der Begutachtung durch das ZMB rund 4,5 Jahre verstrichen; es sei fraglich, ob die Einschätzung der aktuellen Situation entspreche.
Nur der erste der drei genannten Punkte betrifft die hier interessierende Zeitperiode. Im ZMB-Gutachten vom 22. März 2012wurde festgehalten, dass Dr. med. D._ telefonisch nicht erreichbar war, aber dessen Bericht vom 20. Januar 2012 berücksichtigt wurde. Aus diesem geht hervor, dass sich der Versicherte "seit dem 30. Januar 2007 in regelmässiger ambulanter psychiatrischer Behandlung" befinde. Zum vorangegangenen Zeitraum ergibt sich aus den Angaben des Dr. med. D._ nichts zu Gunsten des Versicherten.
3.4. Nach dem Gesagten bilden die genannten Akten - auch mit Blick auf <ref-ruling> - keine zuverlässige Grundlage für die Annahme einer quantitativ eingeschränkten Arbeitsfähigkeit im interessierenden Zeitraum. Angesichts der grossen zeitlichen Distanz von mindestens zehn Jahren sind weitere Abklärungen aussichtslos (antizipierende Beweiswürdigung; <ref-ruling> E. 5.3 S. 236; <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 4b S. 94), weshalb der Eventualantrag auf Rückweisung abzuweisen ist. Die Folgen der Beweislosigkeit hat der Versicherte zu tragen (E. 3.1.2).
Die vorinstanzliche Beweiswürdigung und die Feststellungen betreffend die Arbeitsfähigkeit vom März 2004 bis März 2006 (E. 2) sind nicht offensichtlich unrichtig (unhaltbar, willkürlich: <ref-ruling> E. 8.1 S. 153; Urteil 9C_607/2012 vom 17. April 2013 E. 5.2; zum Begriff der Willkür: <ref-ruling> E. 2.1 S. 18 f. mit Hinweisen). Sie beruhen auch nicht auf einer Rechtsverletzung, weshalb sie für das Bundesgericht verbindlich bleiben (E. 1).
3.5. Dass bei diesem Ergebnis bereits ab März 2004 ein rentenbegründender Invaliditätsgrad (<ref-law>) resultieren soll, ist nicht ersichtlich und macht auch der Beschwerdeführer nicht geltend. Folglich hat das kantonale Gericht einen entsprechenden Anspruch auf Verzugszins ebenfalls zu Recht verneint. Die Beschwerde ist unbegründet.
4.
4.1. Dem Ausgang des Verfahrens entsprechend hat der Beschwerdeführer grundsätzlich die Gerichtskosten zu tragen (<ref-law>). Seinem Gesuch 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>).
4.2. Nach <ref-law> und Art. 2 des Reglements über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht vom 31. März 2006 (SR 173.110.210.3) umfasst die Parteientschädigung die Anwaltskosten und die notwendigen Auslagen für die Prozessführung, wobei sich die Anwaltskosten aus dem Anwaltshonorar und dem Auslagenersatz zusammensetzen. Praxisgemäss wird für einen Normalfall Fr. 2'800.- zugesprochen, Auslagen und Mehrwertsteuer inbegriffen (SVR 2015 BVG Nr. 56 S. 236, 9C_377/2014 E. 5.2; Urteile 9C_918/2012 vom 28. Januar 2013 E. 3.2; 8C_675/2012 vom 7. Dezember 2012 E. 6.2; 8C_370/2010 vom 7. Februar 2011 E. 8.2).
Die Parteientschädigung ist entgegen der vom Rechtsvertreter des Beschwerdeführers eingereichten Honorarnote vom 5. Oktober 2015 nicht auf Fr. 3'348.- festzusetzen. Darin wird insbesondere das (pauschal) geltend gemachte Honorar von Fr. 3'000.- nicht nach Aufwand spezifiziert; zudem fehlen Ausführungen zur Wichtigkeit der Streitsache und zum Umfang der Arbeitsleistung (vgl. Art. 3 Abs. 1 und 3 des genannten Reglements). Mit Blick darauf, dass die Streitsache nicht als überaus schwierig einzustufen ist, erscheint eine Entschädigung in praxisgemässer Höhe als angemessen (vgl. SVR 2015 BVG Nr. 56 S. 236, 9C_377/2014 E. 5.2).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt und Advokat André Baur wird als unentgeltlicher Anwalt bestellt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Dem Rechtsvertreter des Beschwerdeführers wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Kantonsgericht Basel-Landschaft, Abteilung Sozialversicherungsrecht, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 29. März 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Dormann