Sachverhalt:
A.
Der 1956 geborene türkische Staatsangehörige O._ reiste im Oktober 1989 in die Schweiz ein, wo er als Flüchtling anerkannt wurde. Von 1992 bis 1996 absolvierte er eine Ausbildung zum dipl. Sozialpädagogen. Diesen Beruf übte er vom 1. August 1996 bis 21. Februar 1999 in einem Pensum von 80 % aus. Im März 1999 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Basel-Stadt sprach ihm Umschulung zum eidg. dipl. Fahrlehrer zu, die er erfolgreich absolvierte und ihm die Erzielung eines rentenausschliessenden Einkommens ermöglichte (Verfügung vom 9. Februar 2000). Im April 2008 ersuchte O._ um eine Invalidenrente. Nach Abklärungen und Durchführung des Vorbescheidverfahrens ermittelte die IV-Stelle einen Invaliditätsgrad von 20 % und verneinte mit Verfügung vom 6. März 2012 einen Rentenanspruch.
B.
Die dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 13. Mai 2013 gut, soweit es darauf eintrat. Es hob die Verfügung vom 6. März 2012 auf und sprach O._ ab 1. April 2007 eine ganze Invalidenrente zu.
C.
Die IV-Stelle beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, der Entscheid vom 13. Mai 2013 sei aufzuheben und die Angelegenheit sei zu weiteren medizinischen Abklärungen unter Neubeurteilung der Frage der Überwindbarkeit einer posttraumatischen Belastungsstörung an sie selber zurückzuweisen. Zudem ersucht sie um aufschiebende Wirkung der Beschwerde.
O._ lässt auf Abweisung der Beschwerde schliessen, soweit darauf einzutreten sei; eventuell sei die Angelegenheit nicht an die IV-Stelle, sondern an die Vorinstanz zurückzuweisen. Ferner lässt er unentgeltliche Rechtspflege beantragen. Das kantonale Gericht beantragt die Abweisung des Rechtsmittels, das Bundesamt für Sozialversicherungen dessen Gutheissung. Dazu lässt O._ eine weitere Stellungnahme einreichen.

Erwägungen:
1.
1.1. Das Bundesgericht prüft seine Zuständigkeit resp. die Zulässigkeit der bei ihm erhobenen Rechtsmittel von Amtes wegen und mit freier Kognition (<ref-law>; vgl. <ref-ruling> E. 1 S. 96; Urteil 8C_264/2009 vom 19. Mai 2009 E. 1; je mit Hinweisen).
1.2. Nachdem die IV-Stelle im Verwaltungsverfahren einen Rentenanspruch noch verneint hatte, anerkannte sie einen solchen im kantonalen Beschwerdeverfahren, weil sie eine Korrektur des Valideneinkommens für angezeigt hielt. Indessen war das kantonale Versicherungsgericht nicht an die Begehren der Parteien gebunden, und eine Abweisung der Beschwerde des Versicherten hätte keine Reformatio in peius bedeutet (<ref-law>; SR 830.1]). Dass die Verwaltung nun vor Bundesgericht wiederum die (vorläufige) Verneinung des Anspruchs verlangt, stellt somit kein neues Rechtsbegehren (<ref-law>) dar. Zudem kann es entgegen der Auffassung des Versicherten auch nicht als rechtsmissbräuchlich (vgl. <ref-law>) oder mutwillig (<ref-law>; MATTHIAS HÄRRI, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 17 und 20 zu <ref-law>) bezeichnet werden, wenn die IV-Stelle in Bezug auf die Feststellung der Arbeitsfähigkeit erst letztinstanzlich eine fehlende Bundesrechtskonformität geltend macht, zumal davon das Invalideneinkommen und folglich der Rentenanspruch abhängen. Auf die Beschwerde ist daher einzutreten.
2.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (<ref-law>).
3.
Die Vorinstanz hat gestützt auf die Gutachten des Dr. med. F._, Facharzt für Psychiatrie und Psychotherapie, vom 8. Dezember 2008 und 8. Februar 2013 festgestellt, der Versicherte sei ab dem Zeitpunkt des mutmasslichen Rentenbeginns am 1. Februar 2007 in seiner Verweisungstätigkeit als (selbstständiger) Fahrlehrer zu 50 % arbeitsunfähig. Weiter hat sie ihn als hypothetisch zu 80 % Erwerbstätigen ohne Aufgabenbereich qualifiziert und folglich die Invalidität nach der allgemeinen Methode des Einkommensvergleichs bemessen. Für das Vergleichsjahr 2007 hat sie ein Valideneinkommen von Fr. 66'064.40 festgestellt. Für das Invalideneinkommen von Fr. 16'969.- hat sie den in den Vorjahren als selbstständiger Fahrlehrer in einem 70 %-Pensum tatsächlich erzielten Verdienst herangezogen und auf die Restarbeitsfähigkeit von 50 % umgerechnet. Beim resultierenden Invaliditätsgrad von 74 % hat das kantonale Gericht einen Anspruch auf eine ganze Invalidenrente bejaht.
4.
4.1. Die Beschwerdeführerin stellt zunächst die Beweiskraft der Gutachten des Dr. med. F._ in Abrede; sie hält namentlich die darin genannte Diagnose einer posttraumatischen Belastungsstörung (PTBS) für nicht ICD-10-konform.
4.2.
4.2.1. Bei der Beurteilung der Arbeitsunfähigkeit stützt sich die Verwaltung und im Beschwerdefall das Gericht auf Unterlagen, welche von ärztlichen und gegebenenfalls auch anderen Fachleuten zur Verfügung zu stellen sind. Aufgabe des Arztes oder der Ärztin 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. Im Weiteren sind die ärztlichen Auskünfte eine wichtige Grundlage für die Beurteilung der Frage, welche Arbeitsleistungen der Person noch zugemutet werden können (<ref-ruling> E. 4 S. 99 f.). Die Annahme eines invalidisierenden Gesundheitsschadens setzt grundsätzlich eine fachärztliche, lege artis auf die Vorgaben eines anerkannten Klassifikationssystems abgestützte Diagnose voraus (<ref-ruling> E. 6 S. 399 ff.; <ref-ruling> E. 3.2.1 S. 282; Urteil 8C_33/2013 vom 13. Dezember 2013 E. 4.2.1).
4.2.2. 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; vgl. auch SUSANNE BOLLINGER, Der Beweiswert psychiatrischer Gutachten in der Invalidenversicherung unter besonderer Berücksichtigung der bundesgerichtlichen Rechtsprechung, Jusletter vom 31. Januar 2011).
4.2.3. Bei den vorinstanzlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit der versicherten Person handelt es sich grundsätzlich um Entscheidungen über eine Tatfrage (<ref-ruling> E. 3.2 S. 397 ff.), welche das Bundesgericht seiner Urteilsfindung zugrunde zu legen hat (E. 2). Die konkrete Beweiswürdigung stellt ebenfalls eine Tatfrage dar. Dagegen ist die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach <ref-law> Rechtsfrage (<ref-ruling> E. 3.2 und 4 S. 397 ff.; Urteil I 865/06 vom 12. Oktober 2007 E. 4 mit Hinweisen), die das Bundesgericht im Rahmen der den Parteien obliegenden Begründungs- bzw. Rügepflicht (<ref-law> und <ref-law>; <ref-ruling> E. 1.4.1 und 1.4.2 S. 254) frei überprüfen kann (<ref-law>).
4.3.
4.3.1. Dr. med. F._ diagnostizierte eine PTBS gemäss ICD-10: F43.1. Gestützt darauf scheint er implizit eine vollständige Arbeitsunfähigkeit in der angestammten Tätigkeit als Sozialpädagoge (vgl. THOMAS ACKERMANN, Die Bemessung des Invaliditätsgrades, in: Sozialversicherungsrechtstagung 2012, S. 18 f.) angenommen zu haben; explizit attestierte er eine seit "2005/2006" um 50 % reduzierte Arbeitsfähigkeit als Fahrlehrer.
4.3.2. Eine PTBS gemäss ICD-10: F43.1 (<http://www.dimdi.de/static/ de/klassi/icd-10-who/kodesuche/onlinefassungen/htmlamtl2013/block-f40-f48.htm>) entsteht "als eine verzögerte oder protrahierte Reaktion auf ein belastendes Ereignis oder eine Situation kürzerer oder längerer Dauer, mit aussergewöhnlicher Bedrohung oder katastrophenartigem Ausmass, die bei fast jedem eine tiefe Verzweiflung hervorrufen würde. (...) Typische Merkmale sind das wiederholte Erleben des Traumas in sich aufdrängenden Erinnerungen (Nachhallerinnerungen, Flashbacks), Träumen oder Alpträumen, die vor dem Hintergrund eines andauernden Gefühls von Betäubtsein und emotionaler Stumpfheit auftreten. Ferner finden sich Gleichgültigkeit gegenüber anderen Menschen, Teilnahmslosigkeit der Umgebung gegenüber, Freudlosigkeit sowie Vermeidung von Aktivitäten und Situationen, die Erinnerungen an das Trauma wachrufen könnten". Als weitere Kriterien genannt werden Amnesie oder "anhaltende Symptome einer erhöhten psychischen Sensitivität und Erregung (...) mit mit zwei oder mehr der folgenden Merkmale: (a) Ein- und Durchschlafstörungen (b) Reizbarkeit oder Wutausbrüche (c) Konzentrationsschwierigkeiten (d) Hypervigilanz (e) erhöhte Schreckhaftigkeit". Zudem entwickelt sich das Leiden mit einer Latenz von in der Regel höchstens sechs Monaten. "Bei wenigen Patienten nimmt die Störung über viele Jahre einen chronischen Verlauf und geht dann in eine andauernde Persönlichkeitsänderung (F62.0) über" (Dilling/Freyberger [Hrsg.], Taschenführer zur ICD-10-Klassifikation psychischer Störungen, 6. Aufl. 2012, S. 173-175; vgl. auch KRAEMER/HEPP/SCHNYDER, Entstehung, Verlauf und therapeutische Möglichkeiten der posttraumatischen Belastungsstörung, in: Der medizinische Sachverständige, 2007 S. 153; ULRICH SCHNYDER, Posttraumatische Belastungsstörungen [Diagnostik, Prävalenz und Behandlungsmöglichkeiten], in: Psychische Störungen und die Sozialversicherung - Schwerpunkt Unfallversicherung, 2002, S. 101 und 114; Urteil U 368/01 vom 9. April 2002 E. 4a/bb).
4.3.3. Dr. med. F._ ist entsprechend den Angaben des Versicherten davon ausgegangen, dass dieser in der Türkei inhaftiert war und gefoltert wurde. Wann dies stattgefunden hat, ist nicht aktenkundig. Der Versicherte führt selber an, von April bis August 1980 in Gefangenschaft gewesen zu sein. Nachdem er unter falscher Identität gelebt habe, erfolgte im Oktober 1989 die Flucht in die Schweiz. Nach eigenen Angaben trat eine "erste Krise" indessen erst "Ende 1991 oder Anfang 1992" auf. Von September 1992 bis Juni 1996 absolvierte der Versicherte erfolgreich eine Ausbildung zum Sozialpädagogen. Eine psychiatrische Behandlung wurde erstmals im August 1998 aufgenommen (Bericht der psychiatrischen Klinik X._ vom 21. Juli 1999). Schon mit Blick auf diese Gegebenheiten und die Latenz (E. 4.2.2) ist die Einschätzung des Dr. med. F._ nicht nachvollziehbar. Sodann ist eine kritische Auseinandersetzung des Experten mit den subjektiven Angaben und Einschätzungen des Versicherten (vgl. Urteil 9C_421/2013 vom 12. Juli 2013 E. 4.2) nicht ersichtlich: So liess er etwa den Umstand, dass er selber anlässlich des Verlaufsgutachtens "kein depressives Syndrom" mehr ermittelte, während der Explorand in der Selbstbeurteilung bezüglich Somatisierung, Depressivität und Ängstlichkeit zwar verbesserte, aber immer noch erhöhte Werte erzielte, unkommentiert. Weiter leuchtet zwar ein, dass namentlich eine verminderte Belastbarkeit und Konzentrationsfähigkeit "in Krisen" grundsätzlich geeignet ist, die Arbeitsfähigkeit als (selbstständiger) Fahrlehrer herabzusetzen; indessen äusserte sich der Gutachter mit keinem Wort über die Arbeitsfähigkeit in anderen, dem Leiden allenfalls besser angepassten Tätigkeiten (vgl. auch Urteil 9C_624/2013 vom 11. Dezember 2013 E. 3.1.1 mit Hinweisen).
4.4. Nach dem Gesagten bilden die Gutachten des Dr. med. F._ vom 8. Dezember 2008 und 8. Februar 2013 keine genügende Grundlage (E. 4.1.2) für die Feststellung der Arbeits (un) fähigkeit. Die Sache ist praxisgemäss an die Vorinstanz zurückzuweisen. Diese hat über den Gesundheitszustand des Versicherten eine umfassende (d.h. allenfalls auch interdisziplinäre) medizinische Expertise einzuholen (vgl. <ref-law>). Bereits aus diesem Grund ist die Beschwerde gutzuheissen. Die von der Beschwerdeführerin zusätzlich aufgeworfene Rechtsfrage nach der invalidisierenden Wirkung von PTBS resp. der Anwendbarkeit der zu somatoformen Schmerzstörungen entwickelten Rechtsprechung (<ref-ruling> E. 2.2.3 S. 354 f.) braucht daher an dieser Stelle nicht beantwortet zu werden.
5.
Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung der Beschwerde gegenstandslos.
6.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdegegner grundsätzlich die Gerichtskosten zu tragen (<ref-law>; vgl. auch E. 1.2). Seinem Gesuch um unentgeltliche Rechtspflege kann jedoch entsprochen werden (<ref-law>; <ref-ruling> E. 4a S. 202). Es wird indessen ausdrücklich auf <ref-law> hingewiesen, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 13. Mai 2013 aufgehoben. Die Sache wird zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Dem Beschwerdegegner wird die unentgeltliche Rechtspflege gewährt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdegegner auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Advokat Guido Ehrler wird als unentgeltlicher Anwalt des Beschwerdegegners bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'400.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 25. Februar 2014
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Die Gerichtsschreiberin: Dormann