Are there limits for the speed of sound? A maximum or a minimum only? The speed of sound in materials of various states of matter differs a lot.
But does it have fundamental limits?


*

*Is there a maximal possible speed of sound?   

*Is there a minimal possible speed of sound?  

*Is the speed of sound in a material a multidimensional function of many uncorrelated dimesions of material properties, and current state states, such that the function ends up as a vast unknown n-dimensional surface where we not even know in which direction to look for a maximum, and are already happy to find a local maximum at all?

*Obviously, the speed of light in vacuum is a upper limit for the speed of sound in general. But that does not imply that, for a given Material, the material specific speed of light is an upper limit for the  speed of sound in the material.
Of course, in the set of speeds of sound in all materials where it can be measured, there is a maximum and a minimum.
But there are some materials where we can not currently measure the speed of sound, say short lived isotopes available in small numbers of atoms, neutron stars, and other things your university can not order for the laboratory.
From a theoretical perspective, maybe one yould reason about speed of sound independent of existing or potentially existing materials?
 A: The speed of sound is a function of the compressibility of materials and their density:
$$c=\sqrt{\frac{E}{\rho}}$$
Where $E$ is the bulk modulus (sometimes written as $K$) and $\rho$ the density. Compressibility itself depends on the material; for instance diamond, with relatively low density (3.52 g/cm3) and very stiff covalent bonds, has a high speed of sound of around 12 km/s. I suspect that the material of a neutron star is as dense as we can imagine it - so while it might be highly incompressible, it is also very heavy.
There is no theoretical lower limit - heavy materials with extremely weak interactions (high compressibility) can have "very low" speed of sound. Of course sound cannot travel faster than the speed of light, but in reality I can think of no materials systems that get anywhere near that. 
Beryllium (also very light) may have a slightly higher speed of sound - around 12.9 km/s. That may well turn out to be the practical limit.
A: Sound travels fastest in less compressible materials.  But it is also affected by the state of the material, specifically its temperature.
As a mechanical wave, sound must overcome the inertia of the material in which it travels.  Higher temperatures mean greater kinetic energy in the molecules which carry the compression wave, and therefore less inertia for the wave to overcome.
This is illustrated by this formula for the speed of sound in an ideal gas:
\begin{equation}
    v = \sqrt{\frac{\gamma P}{\rho}} = \sqrt{\frac{\gamma  k  T}{M}}
\end{equation}
where:
v is speed of sound;
ρ is the density of the material;
γ is the specific heat ratio (heat capacity ratio) of the material;
k is Boltzmann's constant;
T is the absolute temperature of the material;
M is the molecular mass of the material.
The square of the velocity of a sound wave is directly proportional to the absolute temperature of a gas in which it travels.
A: An equation of state  is a relation of state variables: 
$$
p=p(\rho,\,T,\,\mu,\,\alpha)
$$
where $\mu$ is chemical composition and $\alpha$ the acentricity (itself dependent on $\mu$), the other variables take their normal meaning. There are some equations of state where the dependencies on these variables is non-linear (e.g., the Peng-Robinson eos), so clearly $p$ can be rather complicated (especially when considering the eos of, say, quark-gloun plasmas).
From the equation of state, we can get the speed of sound:
$$
c_s=\sqrt{\frac{\partial p}{\partial\rho}}
$$
So right off the bat, we can define the two limits:


*

*the upper limit, as you say, is clearly $c$ due to the 2nd postulate of SR (e.g., $p=\rho c^2$)

*the lower limit is clearly 0 if $p\neq p(\rho$) (i.e., the pressure is independent of density, not sure of an example)


Typically, when we say the speed of sound for some medium is #m/s, we are specifying the local value to the expected conditions. For example, the speed of sound of air is $\sim340\,\rm m/s$ when considered at standard temperature and pressure (20$^\circ$ C, 1 atm). For temperatures near 0$^\circ$ C, the value varies as
$$
c_{s,air}(T)\simeq20.05\sqrt{T(K)}\,{\rm m/s}
$$
Though, in general, we don't really consider the maxima and minima values of the speed of sound, only the local ones because that value is the one that is most useful to us.
A: The maximum speed of sound is the speed of light - the maximum speed at which "information" can be propagated.
This will occur for an equation of state that satisfies $P = \rho c^2$, where $P$ is the pressure and $\rho$ the density.
Such an incompressible equation of state may be approached in the cores of neutron stars due to the strong nuclear force repulsion between nucleons at very small separations ($< 5\times 10^{-16}$ m). On the other hand it may be that further hadronic or mesonic degrees of freedom will allow the neutrons to form other particles (hyperons, kaons, pions) that will soften the equation of state before this limit is approached.
Note that in an ideal gas (i.e. non-interacting particles) the "hardest" that the equation of state can become will be when $P = \rho c^2/3$ (see below) and thus the maximum sound speed would be $c/\sqrt{3}$ in that instance.
EDIT:
The pressure of an ideal gas from elementary kinetic theory is given by
$$ P = \frac{1}{3} \int n(p) v p\ dp,$$
and the kinetic energy density is given by
$$ u = \int n(p) E_k(p)\ dp,$$
where $n(p)$ is the number density at momentum $p$, $v$ is the particle speed and $E_k$ is the particle kinetic energy. The integral is over all possible particle momenta. 
If the particles are ultra relativistic then $v \simeq c$ and $E_k \simeq pc$. Thus
$$ P = \frac{1}{3} \int n(p) c \frac{E_k}{c}\ dp = \frac{1}{3} u$$
But $\rho = \epsilon /c^2$ where $\epsilon$ is the total energy density (including rest mass) and as the particles become ultrarelativistic we can ignore the rest mass, and say $u \rightarrow \epsilon = \rho c^2$ and hence that
$$ P \rightarrow \frac{1}{3} \rho c^2$$
A: Fresh out of the oven: Physicists have discovered the ultimate speed limit of sound. Quote:

Sound is a wave that propagates by making neighbouring particles
interact with one another, so its speed depends on the density of a
material and how the atoms within it are bound together. Atoms can
only move so quickly, and the speed of sound is limited by that
movement.
Trachenko and his colleagues used that fact along with the
proton-electron mass ratio and the fine structure constant to
calculate the maximum speed at which sound could theoretically travel
in any liquid or solid: about 36 kilometres per second.

