Your parameter $E$ is the [bulk modulus][1], and this is a measure of how compressible the medium is. Easily compressible media like gases have a low value of $E$ while almost incompressible fluids like water have a very high value for $E$. Actually we should really use the symbol $K$ rather than $E$, because $E$ is normally used for the [Young's modulus][2].

And there is the answer to your question. Water does indeed have a higher density than air (by a factor of about 800) but it is much, much less compressible than air so the value of $E$ is [around 20,000 times higher][3]. The end result is that the value of $E/\rho$ is higher in water than air so the speed of sound is greater.

Strictly speaking your equation applies only to gases and liquids. In solids you also need to take account of the [shear modulus][4], and the expression becomes:

$$ v = \sqrt{\frac{K + \tfrac{4}{3}G}{\rho}} $$

where K and G are the bulk modulus and shear modulus respectively. See https://physics.stackexchange.com/questions/101895/why-does-sound-travel-faster-in-iron-than-mercury-even-though-mercury-has-a-high for more details.


  [1]: http://en.wikipedia.org/wiki/Bulk_modulus
  [2]: http://en.wikipedia.org/wiki/Young%27s_modulus
  [3]: http://en.wikipedia.org/wiki/Bulk_modulus#Selected_values
  [4]: http://en.wikipedia.org/wiki/Shear_modulus