Faits :
A.
A.a. La Ville de Genève est propriétaire du Théâtre du Grütli, un espace destiné à la création professionnelle indépendante, et du Théâtre de l'Orangerie, qui accueille durant la période estivale des manifestations artistiques publiques dans le domaine des arts de la scène.
A.b. En avril 2017, le Département de la culture et du sport de la Ville de Genève (ci-après: le Département) a mis au concours, pour une durée de trois ans renouvelable une fois à compter du 1 er juillet 2018, la direction du Théâtre du Grütli, en indiquant qu'une convention de subventionnement et une convention de mise à disposition des locaux seraient conclues avec la direction choisie, qui serait chargée de la programmation, de la gestion et de l'animation (cf. <ref-law>).
X._ et A._ ont déposé leur candidature pour une "direction conjointe". Par courrier du 6 juillet 2017, le Conseiller administratif en charge du Département (ci-après: le Conseiller administratif) leur a annoncé que leur candidature n'avait pas été retenue.
Le 29 août 2017, la Ville de Genève a annoncé la "nomination" de B._ et C._ à la direction. Par la suite, la Ville de Genève, soit pour elle le Département, a conclu avec l'Association Le Grütli - Centre de production et de diffusion des Arts vivants, dénommée "Le Théâtre du Grütli", créée le 9 décembre 2017 pour gérer le Théâtre du Grütli (cf. <ref-law>), une "convention de subventionnement pour les années 2018-2021" (trois saisons), renouvelable une fois. Il y est notamment prévu que la Ville de Genève s'engage à verser à l'Association une aide financière pour les trois saisons (art. 18) et met à disposition les locaux, par le biais d'un contrat de prêt à usage (art. 19). L'Association, autonome quant au choix de son programme artistique et culturel (art. 17), s'engage pour sa part à mettre en oeuvre le projet artistique et culturel développé en annexe (art. 5), ainsi qu'à respecter différentes obligations, notamment en lien avec les tarifs qu'elle pratique (art. 6 à 10). La gestion du personnel est confiée à l'Association, mais la convention réserve la "nomination de la direction" par la Ville (art. 11; cf. aussi art. 14 des statuts de l'Association) (cf. <ref-law>).
A.c. A la mi-juin 2017, le Département a mis au concours, pour trois saisons à partir de l'été 2018, la direction du Théâtre de l'Orangerie.
X._ et A._ ont déposé leur candidature pour une "direction conjointe". Le 8 septembre 2017, le Service culturel du Département les a informés que leur candidature n'avait pas été retenue.
Le 12 septembre 2017, la Ville de Genève a annoncé que D._ avait été nommé à la direction du Théâtre de l'Orangerie. Par la suite, la Ville de Genève a conclu avec l'Association du Théâtre de l'Orangerie, dénommée le "Théâtre de l'Orangerie", une "convention de subventionnement pour les années 2018-2020", au contenu similaire à celle conclue avec l'Association le Théâtre du Grütli (cf. <ref-law>).
B.
Par courrier du 28 septembre 2017 adressé au Conseiller administratif, X._, agissant seul, a "contest[é] le processus de nomination à la tête des deux théâtres et demand[é] l'annulation des nominations auxquelles la procédure a[vait] abouti". Il dénonçait sept dysfonctionnements dans le processus de sélection et sollicitait du magistrat qu'il rende une décision examinant la conformité au droit comme l'opportunité des décisions prises et constatant la violation de ses droits fondamentaux.
Par courrier du 3 novembre 2017, le Conseiller administratif a contesté l'existence des dysfonctionnements évoqués, tout en indiquant qu'il ne lui appartenait pas de rendre une décision. Le 10 novembre 2017, X._ a mis en demeure le Conseiller administratif de rendre une décision, ce que celui-ci a refusé par réponse du 20 novembre 2017.
Le 5 décembre 2017, X._ a saisi la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice), en se plaignant du refus du Conseiller administratif de rendre une décision. Par arrêt du 22 mai 2018, la Cour de justice, après avoir laissé ouverte la question de la qualité pour recourir de X._, a rejeté le recours dans la mesure de sa recevabilité. En substance, la Cour de justice a considéré qu'en l'absence de règles spécifiques de droit public, X._ n'avait pas de droit à une décision en lien avec le processus de nomination des directions des Théâtres du Grütli et de l'Orangerie.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral principalement d'annuler l'arrêt de la Cour de justice du 22 mai 2018 et de le réformer en ce sens qu'un déni de justice commis par le Département soit constaté et la cause renvoyée à celui-ci pour qu'il rende une décision sans tarder. Subsidiairement, il conclut au renvoi de la cause à la Cour de justice pour instruction complémentaire, puis nouvelle décision.
La Cour de justice ne formule aucune observation, s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. La Ville de Genève conclut à l'irrecevabilité du recours, subsidiairement à son rejet. X._ a répliqué. Les parties ont dupliqué, en maintenant leurs conclusions.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle donc librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 186).
1.1. Pour déterminer si, au moment où il se prononce, les conditions de recevabilité sont réunies, le Tribunal fédéral peut prendre en compte des faits postérieurs à l'arrêt attaqué, en dérogation à l'interdiction des faits nouveaux prévue à l'<ref-law> (cf. arrêt 2D_19/2018 du 19 février 2019 consid. 1.1 et les arrêts cités).
En l'occurrence, la Ville de Genève a signalé dans ses déterminations que les saisons des théâtres pour lesquels le processus de "nomination" des directions était litigieux avaient commencé les 28 juin 2018 (Théâtre de l'Orangerie) et 5 septembre 2018 (Théâtre du Grütli). Il peut être tenu compte de ces faits nouveaux non contestés s'agissant de l'examen de la recevabilité du présent recours.
1.2. L'arrêt attaqué confirme le refus du Département de rendre une décision relative au processus de désignation ("nomination") des directions des Théâtres du Grütli et de l'Orangerie. Il s'agit d'une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>), ne tombant pas sous le coup des exceptions de l'<ref-law>. En particulier, le litige ne relève, selon les parties et de prime abord, pas des marchés publics, pour lesquels la voie du recours en matière de droit public n'est ouverte que sous conditions (art. 83 let. f LTF). Le litige ne concerne pas non plus des rapports de travail de droit public (art. 83 let. g LTF), étant relevé qu'il résulte de l'arrêt entrepris et qu'il n'est pas contesté que les directrices du Théâtre du Grütli et le directeur du Théâtre de l'Orangerie ne font pas partie du personnel de la Ville de Genève (cf. art. 1 et 2 du Statut du personnel de la Ville de Genève du 29 juin 2010, LC 21 151). Enfin, et contrairement à ce que laisse entendre l'intimée, le litige ne relève pas de l'art. 83 let. k LTF relatif aux décisions en matière de subventions auxquelles la législation ne donne pas droit, le subventionnement alloué aux théâtres n'étant pas directement en cause. La voie du recours en matière de droit public est partant en principe ouverte.
1.3. Le recours a par ailleurs été formé en temps utile (<ref-law>) et dans les formes prescrites (<ref-law>). Reste à examiner la qualité pour recourir (<ref-law>). Le recourant est le destinataire de l'arrêt attaqué (<ref-law>). Conformément à l'art. 89 al. 1 let. b et c LTF, il faut également qu'il soit particulièrement atteint par la décision attaquée et qu'il ait un intérêt digne de protection à l'annulation ou à la modification de celle-ci. Cet intérêt doit être actuel et exister tant au moment du dépôt du recours qu'à celui où l'arrêt est rendu (<ref-ruling> consid. 1.3.1 p. 143; <ref-ruling> consid. 2.1 p. 41; <ref-ruling> consid. 4.2 p. 299; <ref-ruling> consid. 1.2 p. 365). La jurisprudence a déjà relevé que l'exigence de l'intérêt actuel vaut aussi lorsqu'est invoqué un déni de justice formel: en ce cas, le recourant doit au moins justifier d'un intérêt actuel à ce que son grief (formel) soit examiné, intérêt qui s'apprécie en fonction des effets et de la portée d'une éventuelle admission du recours (cf. <ref-ruling> consid. 1.2 p. 157; <ref-ruling> consid. 2a p. 492; cf. arrêt 5A_752/2016 du 27 janvier 2017 consid. 2.1.1). Il est exceptionnellement fait abstraction de l'exigence d'un intérêt actuel lorsque la contestation peut se reproduire en tout temps dans des circonstances identiques ou analogues, que sa nature ne permet pas de la trancher avant qu'elle ne perde son actualité et que, en raison de sa portée de principe, il existe un intérêt public suffisamment important à la solution de la question litigieuse (cf. <ref-ruling> consid. 1.3.1 p. 143; <ref-ruling> consid. 1.1 p. 208; <ref-ruling> consid. 1.1 p. 103).
1.4. En l'occurrence, l'intimée relève que le recours n'a plus d'objet, car les saisons théâtrales ont commencé. Il est vrai que la jurisprudence part du principe qu'il n'y a plus d'intérêt actuel au recours lorsque le contrat litigieux a déjà été conclu (cf., dans le domaine de la fonction publique, arrêt 8C_596/2017 du 1er mars 2018 consid. 8). Cela étant, une contestation comme celle du cas d'espèce, relative à l'absence de décision concernant la désignation des directions des théâtres municipaux en Ville de Genève, est susceptible de se reproduire en tout temps. Sa nature ne permet en outre pas de la trancher avant qu'elle ne perde de son actualité, l'absence de décision ayant pour corollaire qu'à la suite de la désignation des directions par la Ville, les conventions de subventionnement sont rapidement conclues et les saisons théâtrales débutent. Enfin, la solution de la question litigieuse présente un intérêt public suffisamment important, dès lors qu'est en cause la question du régime applicable à la procédure de désignation des directions qui se retrouvent en charge de la gestion de théâtres municipaux pour plusieurs saisons. Se pose en particulier la question de la portée de l'art. 2 al. 7 de la loi fédérale du 6 octobre 1995 sur le marché intérieur (LMI; RS 943.02) dans un tel cas de figure, qui mérite d'être précisée (cf. infra consid. 6). Les conditions pour faire abstraction de l'exigence d'un intérêt actuel sont donc en l'espèce réunies.
1.5. L'intimée nie par ailleurs la qualité pour recourir du recourant en arguant d'une consorité nécessaire entre celui-ci et A._, qui avait conjointement déposé sa candidature pour les directions litigieuses.
Cette considération n'emporte pas conviction. La notion de consorité nécessaire appartient au droit privé. Si les principes qui la fondent jouent également, dans un certaine mesure, un rôle en procédure administrative, notamment sous l'angle de la qualité pour recourir, la notion n'existe pas, à proprement parler, dans cette matière (cf. <ref-ruling> consid. 5.4 p. 160). En l'espèce, dans la mesure où il n'est pas constaté dans l'arrêt attaqué que les deux candidats ne veulent plus travailler ensemble, il faut admettre un intérêt de fait au recours, ce qui suffit.
1.6. Sur le vu de ce qui précède, il convient d'entrer en matière sur le recours.
2.
2.1. Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit au sens des art. 95 et 96 LTF. Sous réserve des cas visés à l'art. 95 let. c-e LTF, la violation du droit cantonal en tant que tel ne peut être invoquée devant le Tribunal fédéral. Il est néanmoins possible de faire valoir que son application consacre une violation du droit fédéral, comme la protection contre l'arbitraire au sens de l'art. 9 Cst. ou la garantie d'autres droits constitutionnels (<ref-ruling> consid. 6.1 p. 324; <ref-ruling> consid. 1.2 p. 308). Le Tribunal fédéral applique le droit d'office (<ref-law>). Conformément à l'<ref-law>, il ne connaît toutefois de la violation des droits fondamentaux, ainsi que de celle de dispositions de droit cantonal et intercantonal, que si ce grief a été invoqué et motivé par la partie recourante, c'est-à-dire s'il a été expressément soulevé et exposé de façon claire et détaillée (<ref-ruling> consid. 2.4 p. 368; <ref-ruling> consid. 1.3 p. 41; <ref-ruling> consid. 1.2 p. 234).
2.2. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'<ref-law> et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 6 p. 358; <ref-ruling> consid. 1.6 p. 377). Conformément à l'<ref-law>, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. A défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 5.1 p. 356).
3.
Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant se plaint d'une violation de son droit d'être entendu (art. 29 al. 2 Cst.). Il fait grief à la Cour de justice d'avoir retenu, en se fondant sur le site internet de la Ville de Genève et sans lui permettre de participer à l'administration des preuves, qu'il existait différentes salles de spectacle en Ville de Genève, que ces salles n'appartenaient pas toutes à la commune, que les artistes qui s'y produisaient n'étaient pas tous bénéficiaires de subventions et que la Ville de Genève, ainsi que d'autres collectivités publiques, signaient des conventions de soutien conjointes au niveau fédéral.
3.1. Le recourant cite, outre l'art. 29 al. 2 Cst., l'art. 6 par. 1 CEDH. Il n'explique toutefois pas en quoi la présente cause relèverait d'une contestation relative à des droits et obligations de caractère civil au sens de l'art. 6 par. 1 CEDH, ni en quoi cet article, pour autant qu'applicable, aurait été méconnu. Il n'y a partant pas lieu d'examiner la cause sous l'angle de cette disposition (cf. supra consid. 2.1).
3.2. Le droit d'être d'entendu découlant de l'art. 29 al. 2 Cst. comprend le droit, pour le justiciable, de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique (<ref-ruling> consid. 2.3 p. 222; <ref-ruling> consid. 2.2.1 p. 188). Le Tribunal fédéral a ainsi jugé que, lorsqu'une juridiction d'appel entend fonder sa décision sur des preuves nouvelles, elle doit en informer les parties et leur donner l'occasion de s'exprimer à leur sujet (<ref-ruling> consid. 1.1 p. 383; <ref-ruling> consid 2b p. 137). Cependant, les faits notoires n'ont ni à être allégués, ni à être prouvés. Les faits notoires sont ceux dont l'existence est certaine au point d'emporter la conviction du juge, qu'il s'agisse de faits connus de manière générale du public ou seulement du juge. Le Tribunal fédéral a retenu que pour être notoire, un renseignement ne doit pas être constamment présent à l'esprit; il suffit qu'il puisse être contrôlé par des publications accessibles à chacun (<ref-ruling> consid. 4.1 p. 89 s.; <ref-ruling> consid. 5.2 p. 233). En ce qui concerne les informations figurant sur Internet, le Tribunal fédéral a précisé qu'il y a lieu de retenir que seules les informations bénéficiant d'une "empreinte officielle" (par ex: Office fédéral de la statistique, inscriptions au registre du commerce, cours de change, horaire de train des CFF etc.) peuvent en principe être considérées comme notoires (<ref-ruling> consid. 1.2 p. 385).
3.3. En l'occurrence, les faits figurant sur le site officiel de la Ville de Genève que la Cour de justice a pris en compte peuvent être considérés, s'agissant de descriptions concernant les théâtres de la Ville de Genève (par opposé par exemple à un communiqué de presse, cf. arrêt 1C_174/2018 du 13 février 2019 consid. 2), comme notoires. Le seul fait que la Ville de Genève soit la partie intimée en l'espèce ne saurait, contrairement à ce que prétend le recourant, leur ôter cette qualité. La Cour de justice n'a partant pas violé le droit d'être entendu du recourant en mentionnant ces faits dans son arrêt sans interpeller au préalable l'intéressé à leur sujet. Le grief est rejeté.
Pour le surplus, il sera relevé que, sous l'angle des faits retenus, le recourant ne prétend pas que les indications résultant de la consultation du site internet officiel de la Ville de Genève et mentionnées dans l'arrêt entrepris seraient manifestement inexactes ou arbitraires. Il n'y a partant pas lieu de s'en écarter (cf. supra consid. 2.2).
4.
Le litige porte sur la question de savoir si c'est à juste titre que la Cour de justice a confirmé le refus du Département de rendre une décision relative au processus de "nomination" des directions des Théâtres du Grütli et de l'Orangerie. Pour mieux le cerner, il importe de souligner ce qu'implique la "nomination" aux postes de direction des théâtres en cause.
4.1. Il résulte des faits de l'arrêt entrepris et des conventions conclues (cf. supra point A.b et A.c) que la Ville de Genève, après avoir choisi les personnes chargées de la direction des théâtres, a mis à la disposition de celles-ci, outre des fonds, les locaux des Théâtres du Grütli, respectivement de l'Orangerie (art. 19 de chaque convention de subventionnement), pour une durée allant de 2018 à 2021 pour le premier et de 2018 à 2020 pour le second, renouvelable une fois, respectivement deux fois.
A teneur de l'arrêt attaqué, les locaux des Théâtres du Grütli et de l'Orangerie, dont la Ville de Genève est propriétaire, font partie du patrimoine administratif de celle-ci. Cette classification, qui n'est pas contestée, n'a pas à être remise en cause. Relèvent en effet du patrimoine administratif les biens des collectivités publiques qui sont directement affectés à la réalisation d'une tâche publique (cf. <ref-ruling> consid. 6.1 p. 39 s.). En l'occurrence, la promotion de la création artistique, ainsi que de l'activité culturelle, en particulier le soutien à la création et le subventionnement des institutions des arts de la scène, fait partie des tâches publiques de la Ville de Genève (cf. art. 216 al. 1 et 2 de la Constitution de la République et canton de Genève du 14 octobre 2012 [Cst.-GE; RS 131.234], art. 2 al. 1 de la loi genevoise sur la répartition des tâches entre les communes et le canton en matière de culture du 1er septembre 2016 [LRT-2; RS/GE A 2 06]; cf., sur la promotion du cinéma comme tâche d'intérêt public, arrêt 2C_684/2015 du 24 février 2017 consid. 6.2). Les théâtres municipaux sont du reste un exemple type d'établissements relevant du patrimoine administratif (cf. <ref-ruling> consid. 6.1 p. 39 s.; arrêts 2C_719/2016 du 24 août 2017 consid. 3.3.1; 2C_167/2012 du 1 er octobre 2012 consid. 4.2; 1C_312/2010 du 8 décembre 2010 [Théâtre de l'Alhambra à Genève]).
Il résulte en outre des conventions de subventionnement que les directions choisies sont chargées de la gestion des deux théâtres, tant sur le plan artistique qu'administratif.
4.2. Ainsi, les directions désignées se sont vues accorder d'une part l'usage exclusif de biens appartenant au patrimoine administratif de la Ville de Genève pour la durée des conventions, qui sont au reste renouvelables, et d'autre part conférer la gestion des activités théâtrales en ces lieux. C'est à l'aune de ces prérogatives que l'éventuel droit à une décision relative au processus de désignation des directions doit être considéré.
5.
5.1. Devant la Cour de justice, le recourant a allégué que le processus de nomination des directions des théâtres du Grütli et de l'Orangerie devait faire l'objet d'une décision sujette à recours, car l'on se trouvait en présence d'un transfert de monopole communal au sens de l'<ref-law>.
5.2. La Cour de justice a rejeté cette argumentation en relevant que la Ville de Genève n'avait pas la maîtrise sur la création théâtrale professionnelle locale. Elle en a déduit qu'il n'y avait pas en l'espèce de monopole, même de fait, et que l'<ref-law> n'était partant pas applicable. Pour le surplus, elle a ajouté que la "nomination" des directions ne relevait pas des règles sur les marchés publics, ni de celles sur la fonction publique, ce que le recourant ne contestait pas. Pour la Cour de justice, il n'y avait pas de dispositions de droit public spécifiques applicables à la cause, de sorte que le recourant n'avait pas de droit à ce qu'une décision relative au processus de nomination des directions soit prononcée.
6.
Le recourant fait valoir que la Cour de justice a, par ce raisonnement, méconnu l'<ref-law>.
6.1. Selon l'<ref-law>, la transmission de l'exploitation d'un monopole cantonal ou communal à des entreprises privées doit faire l'objet d'un appel d'offres et ne peut discriminer des personnes ayant leur établissement ou leur siège en Suisse (cf. <ref-ruling> consid. 4.1 p. 604; <ref-ruling> consid. 6.1 p. 126).
6.1.1. L'application de l'<ref-law> suppose tout d'abord l'existence d'un monopole cantonal ou communal. La notion de monopole de la loi sur le marché intérieur est réservée à des activités de nature économique (ETIENNE POLTIER, in Commentaire romand - Droit de la concurrence, 2 e éd. 2013, n o 14 ad <ref-law>).
Le champ d'application de l'<ref-law> s'étend tant aux monopoles de droit que de fait (<ref-ruling> consid. 4.1.1 p. 605). Lorsque l'Etat empêche les administrés d'exercer une activité lucrative qu'il se réserve en édictant une norme, on parle de monopole de droit qui, par définition, repose sur une règle topique et expresse (<ref-ruling> consid. 10b p. 222). On appelle monopole de fait la situation où l'Etat, en raison de sa souveraineté sur le domaine public, est en mesure d'exercer seul une activité économique nécessitant un usage particulier du domaine public, sans avoir à créer une base légale pour exclure les particuliers de l'activité en cause; son fondement n'est pas la loi, mais la maîtrise générale sur les biens publics (<ref-ruling> consid. 3b p. 10 s.; <ref-ruling> consid. 10b p. 222; TSCHANNEN/ ZIMMERLI/MÜLLER, Allgemeines Verwaltungsrecht, 4 e éd. 2014, n. 6, p. 436; DUBEY/ ZUFFEREY, Droit administratif général, 2014, n. 1386, p. 492; F RANÇOIS BELLANGER, Marchés publics et concessions, in Zufferey/Stöckli [éd.], Marchés publics, 2012, p. 167 ss, p. 193; DANIEL KUNZ, Verfahren und Rechtsschutz bei der Vergabe von Konzessionen, 2004, p. 21; CLAUDE RUEY, Monopoles cantonaux et liberté économique, 1988, p. 135 ss). Il s'agit souvent de la maîtrise sur les biens du domaine public au sens strict (ensemble des biens qui peuvent être utilisés librement par tout un chacun: <ref-ruling> consid. 2.3.2 p. 284), mais la maîtrise du patrimoine administratif peut aussi donner naissance à un monopole de fait (cf. MOOR/BELLANGER/TANQUEREL, Droit administratif, vol. III, 2 e éd. 2018, p. 185 s.; ETIENNE GRISEL, Liberté économique, 2006, p. 444; CLAUDE RUEY, op. cit., p. 138; d'un autre avis, POLTIER, op. cit., n o 22 ad <ref-law>, qui relève que la maîtrise du patrimoine administratif ne semble pas avoir une extension suffisante pour donner lieu à un monopole de fait).
6.1.2. L'application de l'<ref-law> suppose ensuite une transmission du monopole en faveur du secteur privé (POLTIER, op. cit., n o 24 et n o 44 ad <ref-law>). Cette transmission est en général dénommée concession, mais le terme employé n'est pas décisif en soi au regard du champ d'application de l'<ref-law> (<ref-ruling> consid. 4.1 p. 39; <ref-ruling> consid. 4.1 p. 604). La concession est un acte juridique par lequel l'autorité (le concédant) confère à une personne morale ou physique (le concessionnaire) le droit d'exercer une activité dans un domaine juridiquement réservé à la collectivité publique, autrement dit faisant l'objet d'un monopole étatique de droit ou de fait ou entrant dans les tâches de l'Etat (cf. <ref-ruling> consid. 3.1 p. 37; <ref-ruling> consid. 4.1.1 p. 604). La concession revêt ainsi, d'une part, une certaine stabilité, dont le fondement réside dans sa nature partiellement bilatérale, par opposition à la décision d'autorisation exclusivement unilatérale; d'autre part, elle vise des activités sur lesquelles la collectivité publique dispose d'un monopole (cf. <ref-ruling> consid. 4.1.1 p. 604 s.; <ref-ruling> consid. 9.5 p. 513; <ref-ruling> consid. 3 p. 246). L'octroi d'un usage privatif du domaine public (y compris l'usage exclusif d'un bien du patrimoine administratif) peut par exemple donner lieu à concession (cf. <ref-ruling> consid. 4.1.1 p. 605; <ref-ruling> consid. 6.1 et 6.2 p. 40 ss; cf. Commission de la concurrence, Recommandation du 1 er décembre 2014 à l'attention du Conseil fédéral et de l'Autorité intercantonale pour les marchés publics au sujet des effets de la révision et de l'harmonisation du droit des marchés publics sur la loi fédérale sur le marché intérieur, in DPC 2014/4, p. 809 ss, p. 814).
6.2. En l'occurrence, on se trouve en présence d'une activité économique (la gestion de théâtres) ou à tout le moins à composante économique et donc susceptible de monopole au sens de la loi sur le marché intérieur.
6.3. La question qui se pose est de savoir si, du fait de sa maîtrise exclusive sur les locaux des Théâtres du Grütli et de l'Orangerie, qui font partie de son patrimoine administratif, la Ville de Genève est dans une situation de monopole de fait par rapport à l'activité de gestion de ces théâtres.
La Cour de justice a considéré qu'il n'y avait pas de monopole de fait en l'espèce, car la Ville n'avait pas la maîtrise de la création professionnelle locale, puisqu'il existait différentes salles de spectacle, qui n'étaient pas toutes propriétés de la Ville, et que tous les artistes n'étaient pas subventionnés par la commune.
Cette position ne peut être suivie. Nier l'existence d'un monopole de fait sur la base de ces constats revient en effet à définir le monopole de fait uniquement par rapport à la question de l'exclusivité de l'activité économique exercée, sans considération pour la notion de maîtrise sur le bien public visé. Or, c'est cette maîtrise qui caractérise le monopole de fait, en tous les cas lorsque l'activité doit s'exercer en ce lieu. Ainsi, la Ville de Genève n'a certes pas le monopole de la création artistique sur tout son territoire; par rapport aux Théâtres du Grütli et de l'Orangerie, elle est néanmoins en situation d'exclusivité du fait que ces bâtiments font partie du patrimoine administratif et que l'activité théâtrale en ces lieux dépend uniquement d'elle. Il convient d'admettre qu'une telle situation relève de la notion de monopole de fait. Cette solution se justifie d'autant plus en l'espèce qu'en octroyant des aides financières aux directions des deux théâtres, la Ville de Genève les place dans une position concurrentielle nettement avantageuse par rapport à des compagnies et théâtres privés qui ne reçoivent aucune subvention, puisque les deux théâtres peuvent pratiquer des tarifs préférentiels - ils en ont même l'obligation à teneur des conventions conclues (cf. <ref-law>) -. On se trouve donc en présence en l'espèce de deux monopoles communaux de fait.
La condition du transfert du monopole en faveur d'un partenaire privé est en outre réalisée dans les deux cas. A noter que, selon les conventions conclues, ces partenaires privés se sont vus conférer un usage exclusif des locaux (au détriment de tiers) pour une durée qui n'est pas négligeable (trois saisons pour chaque théâtre, avec possibilité de renouveler les conventions). Bien que les conventions n'en portent pas le nom, elles comportent ainsi des caractéristiques propres à une concession. Au vu de ces éléments, les conditions d'application de l'<ref-law> sont réunies, contrairement à ce qu'a retenu la Cour de justice.
6.4. Les conséquences de l'applicabilité de l'<ref-law> pour la présente cause sont les suivantes.
6.4.1. L'<ref-law> impose deux exigences (découlant du droit des marchés publics) à la transmission de l'exploitation d'un monopole cantonal ou communal: un appel d'offres et l'interdiction de discriminer des personnes ayant leur établissement ou leur siège en Suisse. La mise en place d'un appel d'offres implique certaines obligations procédurales. La collectivité publique doit non seulement organiser une procédure permettant aux personnes (physiques ou morales) privées intéressées par l'exploitation dudit monopole de déposer une offre, mais aussi attribuer la concession par le biais d'une décision contre laquelle des voies de droit doivent être ouvertes (cf. art. 9 al. 1 et 2 LMI; <ref-ruling> consid. 4.1.2 p. 606; <ref-ruling> consid. 6.4.1 p. 129; <ref-ruling> consid. 4.1 p. 52; arrêt 2C_351/2017 du 12 avril 2018 consid. 3.4). Quant à l'interdiction de discriminer, elle s'applique non seulement à la procédure d'appel d'offres stricto sensu, mais aussi à la détermination des critères de sélection et au choix du concessionnaire; elle impose aussi le respect du principe de transparence, qui est son corollaire (ATF <ref-ruling> consid. 6.4.1 p. 129).
Il convient toutefois de ne pas perdre de vue la position intrinsèquement différente de l'autorité lors de la passation d'un marché public par rapport à celle exercée lors du transfert d'un monopole. Contrairement au marché public dans lequel la collectivité publique, endossant le rôle de "consommateur", acquiert auprès d'une entreprise privée, en contre-partie du paiement d'un prix, une prestation dont elle a besoin pour exécuter ses tâches publiques (ATF <ref-ruling> consid. 6.3.3 p. 129; <ref-ruling> consid. 1.2.1 p. 117; <ref-ruling> consid. 6b p. 212 s.), l'attribution d'une concession de monopole cantonal ou communal implique que l'autorité concédante se trouve dans un rôle "d'offreur" ou de "vendeur", puisqu'elle cède, moyennant une redevance et diverses prestations annexes, le droit d'utiliser le domaine public à des fins commerciales (ATF <ref-ruling> consid. 6.3.3 p. 129; <ref-ruling> consid. 4.2 p. 53; <ref-ruling> consid. 6b p. 213). Il n'y a pas de droit à l'obtention d'une concession de monopole, car la collectivité publique reste libre d'exercer elle-même l'activité en cause (cf. ATF <ref-ruling> consid. 6.3.3 p. 129; <ref-ruling> consid. 2.2.1 p. 108 s.; <ref-ruling> consid. 3b p. 11). Ces différences justifient de laisser à la collectivité publique une plus grande liberté dans le choix des critères à remplir par le concessionnaire et des conditions qu'elle peut lui imposer dans l'exercice du monopole qu'en matière de marchés publics (cf. ATF <ref-ruling> consid. 6.3.3 p. 129; <ref-ruling> consid. 2.2.1 p. 108 s.; <ref-ruling> consid. 3b p. 11).
6.4.2. En l'occurrence, dès lors qu'il y a eu transfert d'un monopole de fait, l'intimée se devait de respecter les exigences précitées, notamment procédurales. C'est partant à raison que le recourant se plaint de ce que la Ville de Genève a "nommé" chaque direction sans rendre de décision susceptible de recours, cet acte constituant en réalité une attribution de concession.
6.5. C'est en vain que l'intimée s'oppose au prononcé d'une décision.
6.5.1. L'intimée soutient que la gestion de son patrimoine administratif relève exclusivement du droit privé. A tort. Ainsi que le lui a déjà signifié le Tribunal fédéral (cf. arrêt 2C_167/2012 du 1 er octobre 2012 consid. 4.4), l'intimée, en tant que collectivité, est tenue au respect des principes de base du droit administratif dans la gestion de son patrimoine administratif (cf. art. 35 al. 2 Cst.). Sa liberté d'appréciation dans le choix de la personne à laquelle elle accorde notamment un usage exclusif du domaine public, bien qu'elle soit importante, n'est ainsi pas illimitée, quel que soit le moyen par lequel elle accorde cet usage (cf. arrêt 2C_167/2012 du 1 er octobre 2012 consid. 4; cf. MOOR/ POLTIER, Droit administratif, vol. II, 3e éd. 2011, p. 417, 443; MARC-OLIVIER BESSE, L'investiture du délégataire, in Favre/Martenet/Poltier (éd.), La délégation d'activités étatiques au secteur privé, Genève; Zurich 2016, p. 67 ss, p. 101, 115-116; JEAN-BAPTISTE ZUFFEREY, Le droit des PPP: état des lieux, in Jean-Baptiste Zufferey [éd.], Marchés publics 2010, p. 257 ss, p. 278). En d'autres termes, même lorsqu'elle entend agir comme un partenaire de droit privé, la collectivité demeure contrainte de respecter les principes généraux de l'activité administrative (cf. <ref-ruling>; arrêt 1P.342/2006 du 9 mars 2007 consid. 2.2), parmi lesquels figurent l'interdiction de l'arbitraire, l'égalité de traitement et la proportionnalité, de même que le devoir de l'autorité d'adopter une attitude neutre et objective (cf. <ref-ruling> consid. 7.1 p. 44; <ref-ruling> consid. 6.4.1 p. 208; cf. arrêts 2C_719/2016 du 24 août 2017 consid. 3.6; 2C_684/2015 du 24 février 2017 consid. 6.2).
On peut certes se demander s'il faudrait déduire en l'espèce de ces exigences minimales un droit à une décision ouvrant l'accès au juge pour permettre d'en vérifier le respect (théorie dite des "deux niveaux"; cf. MOOR/POLTIER, op. cit., p. 446-449; MARC-OLIVIER BESSE, op. cit., p. 116; ZUFFEREY, op. cit., p. 278). La question souffre toutefois de demeurer indécise, dès lors que le prononcé d'une décision s'impose en raison de l'<ref-law>.
6.5.2. La Ville de Genève s'oppose par ailleurs au prononcé d'une décision en relevant que les dossiers du recourant n'ont pas même été retenus pour le second tour lors des sélections des candidats. Celui-ci serait en outre forclos à se plaindre d'une irrégularité de la procédure de nomination, car il n'aurait pas réagi dans les délais fixés par l'<ref-law>. Ces arguments auraient éventuellement pu être opposés au recourant dans le cadre du recours contre la décision qui aurait dû être rendue. Dit autrement, ils concernent une autre phase de la procédure et sont extérieurs au présent litige. Ils ne sont partant pas propres à remettre en cause la conclusion qu'une décision relative à la désignation des directions devait en l'espèce être prononcée.
6.5.3. De même, l'argument de la Cour de justice, appuyé par l'intimée, relatif à une violation du principe de la bonne foi par le recourant, qui aurait attendu l'issue de la procédure de sélection pour se plaindre de dysfonctionnements, n'a pas à être examiné plus avant dans le cadre du présent litige, car il relève du fond.
6.6. En définitive, le grief du recourant tiré de la violation de l'<ref-law> doit être admis. Les exigences découlant de cette disposition (lue conjointement avec l'art. 9 al. 1 et 2 LMI) conduisent à l'admission du recours, en ce sens que la Ville de Genève devait rendre une décision attaquable en lien avec la "nomination" des directions des Théâtres du Grütli et de l'Orangerie. Cette conclusion rend superflu l'examen des autres griefs du recourant, en particulier de celui tiré de la violation de l'art. 29a Cst. qui garantit l'accès au juge (voir notamment sur cette disposition et concernant le subventionnement du cinéma dans le canton de Genève, arrêt 2C_684/2015 du 24 février 2017 consid. 6.5).
7.
Les considérants qui précèdent conduisent à l'admission du recours. L'arrêt attaqué doit être annulé. Il est constaté que la Ville de Genève aurait dû attribuer une concession par le biais d'une décision.
Comme les directions ont déjà été nommées et les contrats de subventionnement conclus, la procédure ne peut désormais concerner que l'éventuel caractère illicite de la décision (cf., par analogie avec les marchés publics, <ref-ruling> consid. 4.6 p. 31). En l'absence d'un tel acte et des constatations de fait qui en découlent, le Tribunal fédéral ne peut toutefois pas se prononcer sur cette question. Dans ces conditions, il convient de renvoyer la cause au Département, afin qu'il rende une décision dans laquelle il constatera les règles et les critères suivis lors du processus de nomination des directions des Théâtres du Grütli et de l'Orangerie, permettant ainsi le cas échéant au recourant de se plaindre de leur éventuelle illicéité, à supposer qu'il remplisse les conditions procédurales pour ce faire (cf. notamment consid. 6.5.2 et 6.5.3), ce qu'il n'appartient pas au Tribunal fédéral de vérifier.
La Ville de Genève, qui succombe et défend un intérêt patrimonial puisqu'est en cause le transfert d'un monopole communal au sens de la LMI, supportera les frais judiciaires pour la procédure devant le Tribunal fédéral (art. 66 al. 1 et 4 LTF). Ayant obtenu gain de cause avec l'aide d'un mandataire professionnel, le recourant a droit à des dépens (<ref-law>), qu'il convient de mettre à la charge de la Ville de Genève (<ref-law>). La cause est renvoyée à la Cour de justice pour qu'elle statue à nouveau sur les frais et dépens de la procédure accomplie devant elle (cf. art. 67 et 68 al. 5 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis.
2.
L'arrêt de la Cour de justice du 22 mai 2018 est annulé.
3.
La cause est renvoyée à la Ville de Genève, Département de la culture et du sport, pour qu'elle procède dans le sens des considérants.
4.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de la Ville de Genève.
5.
La Ville de Genève versera au recourant une indemnité de 2'500 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
6.
La cause est renvoyée à la Cour de justice pour nouvelle décision sur les frais et dépens de la procédure devant elle.
7.
Le présent arrêt est communiqué au mandataire du recourant, à la Ville de Genève, Département de la culture et du sport, et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lausanne, le 27 mai 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber