  We consider black holes in anti-de Sitter space AdS_{p+2} (p = 2,3,5), which
have hyperbolic, flat or spherical event horizons. The $O(\alpha'^3)$
corrections (or the leading corrections in powers of the eleven-dimensional
Planck length) to the black hole metrics are computed for the various
topologies and dimensions. We investigate the consequences of the stringy or
M-theory corrections for the black hole thermodynamics. In particular, we show
the emergence of a stable branch of small spherical black holes. We obtain the
corrected Hawking-Page transition temperature for black holes with spherical
horizons, and show that for p=3 this phase transition disappears at a value of
$\alpha'$ considerably smaller than that estimated previously by Gao and Li.
Using the AdS/CFT correspondence, we determine the $S^1 x S^3$ N=4 SYM phase
diagram for sufficiently large `t Hooft coupling, and show that the critical
point at which the Hawking-Page transition disappears (the correspondence point
of Horowitz-Polchinski), occurs at $g_{YM}^2N \approx 20.5$. The d=4 and d=7
black hole phase diagrams are also determined, and connection is made with the
corresponding boundary CFTs. Finally, for flat and hyperbolic horizons, we show
that the leading stringy or M-theory corrections do not give rise to any phase
transition. For horizons compactified to a torus $T^p$ or to a quotient of
hyperbolic space, $H^p/\Gamma$, we comment on the effects of light winding
modes.
