What's so special about AdS? This question is coming from someone who has very little experience with M-Theory but is intrigued by the AdS/CFT correspondence and is beginning to study it.
Why is the gauge/gravity duality discussed almost always in the context of anti-deSitter space? What is unique about it? What are the difficulties in studying it in Schwarzschild, deSitter, etc.? References to work done on the gauge/gravity duality in these more physical spacetimes would be much appreciated.
 A: AdS$_d$ in any space-time dimension $d\geq 2$ is maximally symmetric with isometry group so(d-1,2) (for Minkowski signature).
This group coincides with the conformal group in d-1 dimensions (again for Minkowski signature).
For instance, for AdS$_5$ you obtain the isometry group so(4,2), which is the conformal group in 4 dimensions. This matching is a slightly trivial consistency check that something like an AdS$_5$/CFT$_4$ correspondence can work.
Another special feature of AdS as opposed to dS is that it provides a stable vacuum in most theories (whereas dS is only meta-stable), and that it is compatible with SUSY (whereas dS is not).
Spaces that asymptote to AdS have very special properties, too. Brown and Henneaux showed in d=3 that any consistent quantum theory of gravity must be dual do a 2-dimensional conformal field theory, in the sense that the Hilbert space must fall into irreducible representations of two copies of the Virasoro algebra, with central charge determined by Newton's constant and the cosmological constant. This was an important precursor of the AdS/CFT correspondence, where such a duality is realized explicitly (but in higher dimensions).
Minkowski space is also maximally symmetric and stable, but not as susceptible to holography as AdS. 
In summary, AdS spaces are simple and have interesting physical properties, which is why they are used quite frequently.
A: AdS space is basically just hyperbolic space, with a time direction. Here's a nice geometrical fact. Consider 2d hyperbolic space in the Poincaré disc model. (Generalizing to higher dimensions is straightforward.) The metric is $ds^2 = \frac{dr^2 + r^2 d\theta^2}{(1-r^2)^2}$. The corresponding area element is $\frac{rdrd\theta}{(1-r^2)^2}$. So consider the circle at fixed $r = r_0$. This has circumference $2\pi r_0\frac{1}{1-r_0^2}$, and area $2\pi \int_0^{r_0} \frac{rdr}{(1-r^2)^2}$. For $r_0 = 1 - \epsilon$, with $\epsilon \ll 1$, these are $\frac{\pi}{\epsilon} - \frac{\pi}{2} + {\cal O}(\epsilon)$ and $\frac{\pi}{2\epsilon} - \frac{\pi}{2} + {\cal O}(\epsilon)$, respectively.
What does this mean? It means that, for circles large compared to the curvature radius of the space, perimeter and area scale in the same way as you make the circle larger. (As opposed to flat space, where one scales like the square of the other.) I think this is a hint about holography; in some sense, AdS is the space in which holography becomes almost trivial, because $d$ and $d-1$ dimensional volumes are almost identical, which is why we understand holography much better in AdS.
(Of course, this isn't unrelated to the ideas about conformal symmetry, etc. But I think this geometric fact sheds some light and is easy to understand without getting into details of physics.)
A: There are some extensions of the AdS/CFT correspondence, so it is more accurate to call the more general set of dualities the gauge/gravity correspondence. In all such dualities one has a gravity dual of some quantum field theory, and the theory in question determines the boundary conditions on all the bulk fields (including the asymptotics of the bulk geometry). States of those theories correspond to small fluctuations (normalizable modes) moving in the bulk of that spacetime, and the vacuum state usually corresponds to the maximally symmetric ("empty") space. There are many such examples which are not AdS even asymptotically, though sadly asymptotically dS is not yet one of them (partially because it is not clear what the expression "asymptotically dS" really means). Asymptotically flat examples, alas with linear dilaton background, do exist.
But, within the set of all holographic dualities there is something special in spaces which are asymptotically AdS. Those correspond to theories which become conformal at short distances. Using Wilsonian language, those are theories whose renormalization group flow can be continued to all energy scales, so they are completely well-defined quantum field theories without a cutoff. Such field theories are defined as relevant deformations of fixed points in the UV, and the holographic translation of that statement is that the gravity dual is asymptotically AdS.
Continuing with the Wilsonian language, usually one needs to use QFT only as an effective field theory, and it is then inherently defined with an UV cutoff. Such more general quantum field theory (defined only up to certain energy scale) correspond to instances of gauge-gravity duality which are not asymptotically AdS. The correspondence between EFT with a cutoff and non-asymptotically-AdS space (at least on some occasions dubbed the "non-AdS/non-CFT correspondence") is less well-understood than AdS/CFT (with the amount of work on AdS/CFT, this applies to many other subjects...). But, it is a very useful and interesting subject, in some ways more so than the original AdS/CFT correspondence, the one that opened the flood gates.
In any event, the type of boundary conditions imposed on the space is only restrictive when discussing global questions. Any local process you are interested in (say, the formation and evaporation of black holes) can be embedded in asymptotically AdS space with an arbitrarily small cosmological constant. I wouldn't then think about the set of examples provided by AdS/CFT as "unphysical" in any way - it may not address all the possible questions one may be interested in, but it the best way to address of whole bunch of fascinating ones.
A: I'm going to provide a possible controversial answer, in an attempt to provoke some discussion. I do this in good faith, and in the belief that what I state are true, and back with references (comments of "citation needed" will be very handy). I context this with: I'm a condensed matter theorist, and I think the usual exposition of AdS/CFT has the cart before the horse. I will take a long detour, but hopefully I will come back at the end and answer the actual question.
Let's start with a spin 1/2 chain on a 1D lattice, infinite in extent. The Hilbert space is a product of 2 dimensional spaces. Let the Hamiltonian be anti-ferromagnetic Ising with an external magnetic field, so that at a critical field strength we will get a quantum phase transition from anti-ferromagnetic to ferromagnetic. We deal only with the ground state (i.e. at zero temperature). Let's then make a couple of observations: away from the phase transition, the correlation length is finite, and the entanglement entropy of any given block of length $L$ is asymptotically a constant (as $L \rightarrow \infty$); at the phase transition, the correlation length is infinite, and the entanglement entropy goes as $\log(L)$. Note that these are quite special features of the ground state, since the typical (defined as average over the canonical Haar measure) state has entanglement entropy which scales as $L$.
Therefore, instead of writing the ground state with full generality $$\left| \Omega \right\rangle = \sum_{s_1,s_2,\ldots} c_{s_1,s_2,\ldots} \left|s_1\right\rangle\otimes\left|s_2\right\rangle\otimes\ldots$$ where we would have to specify the matrix $c$ with an exponentially large number of dimensions (spanning the full Hilbert space), we're going to restrict our attention to so-called Matrix Product States (MPS) with the form: $$\left|\Omega\right\rangle = \sum_{s_1,s_2,\ldots} \mathrm{Tr}\left(\hat A^{s_1} \hat A^{s_2} \ldots \right) \left|s_1\right\rangle\otimes\left|s_2\right\rangle\otimes\ldots$$ where the matrices $\hat A^{s_i}$ are arbitrary matrices of dimension $m$. Essentially, we're staring in the corner of Hilbert space which is spanned by a linearly increasing number of dimensions. Now, as $m \rightarrow \infty$ we recover the full Hilbert space, but away from the critical point, a finite $m$ suffices to fully (exactly) describe the ground state, because of the prior point about finite entanglement entropy; essentially, the dimension $m$ controls how much entanglement is possible between adjacent sites, and the MPS ansatz fully spans all such states.
But, as mentioned, the entanglement in a critical state is not bounded. In this case, we can use a different ansatz, the Multi-scale Entanglement Renormalisation Ansatz (MERA). The construction is difficult to describe in words, but easier in pictures. If we use tensor network diagrams (first identified by Penrose and called spin networks), we depict each tensor as a blob with a number of legs equal to its rank. Treating the matrices $\hat A^{s_i}$ as 3-rank tensors (one extra due to the spin index), we can draw the MPS as: 
 
where the lower legs are the spin indices. The MERA is then

(but imagine that the "tree" continues upwards without end). The essence is that we reify coarse graining (i.e. renormalisation) into the ground state description by a tree of disentanglers and coarse graining. Again, if we do this right, this can describe the ground state with perfect accuracy.
These tensor network diagrams also give a picturesque reason for why the entanglement entropy scales as a constant and as $\log(L)$ respectively. The argument is that the entanglement is localised at the boundary of a block (as it has to, since each connection in that network can only support a finite amount of entanglement), but the "boundary" actually scales differently in the two cases: the the non-critical case, it is just the edges of a 1D chain, which clearly don't care about the bulk; in the critical case, it needs to include not only the bottom layer, but all the layers above it, and there are $\log(L)$ layers. 
So far, everything is basically (up to corner cases) true. Let's now turn to more conjectural/interpretational stuff. Focus on MERA. Notice that if we treat it as a space, then a natural distance measure is the number of "hops" we need to do from one vertex to another; notice also, that in the continuum limit this is a homogeneous hyperbolic space, i.e. AdS. In the original Ising model, at the critical point, the field theory should be conformally invariant, and thus be a CFT. This is all but AdS/CFT, except we haven't specified that the MERA coefficients are computed by a quantum gravitational theory (it probably can't be, I think... the central charge is 1, and nothing is supersymmetric). 
Now, at this point, you might think "Aha! See? AdS/CFT is of primary importance to even mundane things like condensed matter!" However, I'd like to present some evidence that actually, AdS/CFT is a mundane consequence of a very clever idea, which is to geometrically interpret the information in a ground state.
Let's consider instead an interacting fermion system in 1D. The usual electrons with Coulomb repulsion will do. It is known that the physical ground state is that of non-interacting solitons of fractionalised electrons: holons (carrying the charge) and spinons (carrying the spin). Our ansatz will then be that of MERA, but at a certain depth in the tree, we duplicate everything above it --- so that we end up with two 1D systems, one for holons and one for spinons. In the geometric picture above, it will be as if we glued an extra AdS space onto the usual one, so that we get a fork. 
The reason this suggests that actually the ground state should come first and the holography principle second is two fold:


*

*Holography only holds for special states like the ground state, where the entanglement entropy scales sub-bulk.

*The internal AdS space might not be AdS, or even admit any sort of nice geometrical picture, and even if it does, it might not be given by some sort of Lagrangian based field theory.


So, back to the question: "what is special about AdS?" Other answers will no doubt focus on the special geometry that makes the maths work, but I would answer that the key is never the inner space, but the boundary: the (super-)CFT. The inner space, in this case, AdS, just comes along for a ride. If we had some other kind of boundary theory, we'd have some other kind of inner space, or not a space at all!
References:
Seminal (?) paper on correspondence between MERA and holography: http://arxiv.org/abs/0905.1317
Branching MERA as exotic holography: http://pirsa.org/10110076
A: The $AdS$ in a Euclidean form is a is a hyperbolic space.  In two dimensions hyperbolic plane ${\cal H}^2$ is a simply connected manifold with constant Gaussian curvature $-1$.  The two dimensional $AdS_2$ holds near the event horizon of a black hole, which is the Poincare disk ${\cal D}^2~=~\{z:|z|~<~z_0\}$, and related to the Rindler spacetime the upper half plane ${\cal H}^2~=~\{z:Im(z)~>~0\}$.  The group of isometries $Iso({\cal H}^2)$ is the set of smooth transformations $z^\prime~=~gz$ which satisfy the hyperboloid metric for $s~=~s(z,~gz)$.  The half plane and the Poincar{\'e} disk are related by a conformal transformation, so the transformation of coordinates are given by
the same group. In the half plane the isometries are the fractional linear transformations, or modular group
$$
g:{\cal H}~\rightarrow~{\cal H},~z:~\mapsto~gz:~=~{{az~+~b}\over{cz~+~d}},~\left(\matrix{a &
b\cr c & d}\right)~\in~SL(2,~{\bf R}).
$$
The matrices $g$ and $-g$ are the same fractional linear transformations, so the isometries  $Iso({\cal H}^2)$ may be identified with the projective Klein group $PSL(2,~{\mathbb R})~=$ $SL(2,~{\mathbb R})/\{\pm 1\}$.  The group is restricted further by the isotropy subgroup which leaves elements of ${\cal H}^2$ unchanged $z~=~gz$.  Any such $g~\in~PSL(2,~{\mathbb R})$ defines the $SO(2)$ rotation group.  Then ${\cal H}^2~=~PSL(2,~{\mathbb R})/SO(2)$.
The discrete structure, or $PSL(2,{\mathbb Z})$ is manifested in the tessellation symmetry of the hyperbolic half-plane or disk.  These symmetries are seen in the Escher prints called limit circles.  These discrete structures give the MERA structure which Genneth references.  The “piling up” of structure towards the boundary is a renormalization of the Ising spin system, for spins at the vertices in the tessellation.  What follows is in part a brief outline of the discrete coset $AdS$ completion due to Charles Frances.
http://www.math.u-psud.fr/~frances/
The boundary space $\partial AdS_{n+1}$ is a Minkowski spacetime, or a spacetime $E_n$ that is simply connected that with the $AdS$ is such that $AdS_{n+1}\cup E_n$ is the conformal completion of $AdS_{n+1}$ under the discrete action of a Kleinian group.  For the Lorentzian group $SO(2,~n)$ there exists the discrete group $SO(2,n,Z)$ which is a Mobius group.  For a discrete subgroup $\Gamma$ subset $SO(2,~n,~Z)$ that obeys certain regular properties for accumulation points in the discrete set $AdS_{n+1}/\Gamma$ is a conformal action of $\Gamma$ on the sphere $S_n$.  This is then a map which constructs an $AdS/CFT$ correspondence.  Given that $AdS_n~=~O(n,2)/O(n,1)$ this coset structure is a Clifford-Klein form, or double coset structure.
The lightlike geodesics in $E^n~=~M^n$, the Minkowski spacetime, are copies of $RP^1$, which at a given point p define a set that is the lightcone $C(p)$.  The point p is the projective action of $\pi(v)$ for $v$ a vector in a local patch $R^{n,2}$ and so $C(p)$ is then $\pi(P\cap C^{n,2})$, for $P$ normal to $v$, and $C^{n,2}$ the region on $R^{n,2}$ where the interval vanishes. 
The space of lightlike geodesics is a set of invariants and then due to a stabilizer on $O(n,2)$, so the space of lightlike curves $L_n$ is identified with the quotient $O(n,2)/P$, where $P$ is a subgroup defined the quotient between a subgroup with a Zariski topology, or a Borel subgroup, and the main group $G~=~O(n,~2)$.  This quotient $G/P$ is a projective algebraic variety, or flag manifold and $P$ is a parabolic subgroup.  The natural embedding of a group $H~\rightarrow~G$ composed with the projective variety $G~\rightarrow~G/P$ is an isomorphism between the $H$ and $G/P$.  This is then a semi-direct product $G~=~P~\rtimes~ H$.  For the $G$ any $GL(n)$ the parabolic group is a subgroup of  upper triangular matrices. This is the Heisenberg group.
This connection to Heisenberg groups and parabolic groups is particularly interesting.  The structure here has a $\theta$-function realization, and is related to the density of states in string theory.  This leads one in my opinion into some very deep structure which is not at all completely explored.
