I start from the Navier-Stokes equations (no external force, inviscid).
\begin{equation} \frac{\partial \vec{u}}{\partial t} + \vec{u} \cdot \nabla \vec{u}= \frac{1}{ \rho }\nabla p \end{equation}
\begin{equation} \frac{\partial \rho}{\partial t} + \nabla \cdot (\rho \vec{u}) = 0 \end{equation}
I then use a perturbation method to find the linear wave equation. I assume that my fluid (in this case is air) is at rest to begin with, with
\begin{align*} \rho &= \rho_0 = \text{constant}\\ p &= p_0 = \text{constant}\\ \vec{u} &= \vec{0} \end{align*}
and then a small perturbation happens, $\epsilon << 1$.
\begin{align*} \rho &= \rho_0 + \epsilon \tilde{\rho}\\ p &= p_0 + \epsilon \tilde{p} \\ \vec{u} &= \epsilon \tilde{\vec{u}} \end{align*}
Putting these perturbed variables into my Navier-Stokes equations I get
\begin{equation} \frac{\partial\tilde{\rho}}{\partial t} + \rho_0 \nabla \cdot \tilde{\vec{u}} + O(\epsilon) = 0 ~~~~\text{(1)} \end{equation} and \begin{equation} \rho_0 \frac{\partial \tilde{\vec{u}}}{\partial t} - \nabla \tilde{p} + O(\epsilon) = 0 ~~~\text{(2)} \end{equation}
I use the vector identity $\nabla ( \nabla \cdot \vec{v}) = \nabla \times \nabla \times \vec{v} - \nabla^2 \vec{v}$ with the fact that the flow is irrotational, $ \nabla \times \vec{u} = 0$ to get the following from $1$:
\begin{equation} \nabla \frac{\partial \tilde{\rho}}{\partial t} - \rho_0 \nabla^2 \tilde{\vec{u}} + O(\epsilon) = 0 \end{equation}
Now adding this and $2$ together I get
\begin{equation} \rho_0 \frac{\partial^2 \tilde{\vec{u}}}{\partial t^2} - \rho_0 \nabla^2 \tilde{\vec{u}} = 0 \end{equation}
Whereas I'm looking for
\begin{equation}\label{lin_wave_eq} \nabla^2 \vec{u} = \frac{1}{c^2} \frac{\partial^2\vec{u}}{\partial t^2} \end{equation}
So I'm missing a constant ($c^2$, specifically). Any ideas where I am going wrong?
You missed a 1st-order Taylor expansion for the pressure. In addition, you write incorrectly the pressure term in the momentum equation. I summarize all the steps. The Euler equations are
$$\begin{align} & \frac{\partial \rho}{\partial t} + \nabla \cdot (\rho \mathbf{u}) = 0,\\ & \rho\frac{\partial \mathbf{u}}{\partial t} + \rho\mathbf{u} \cdot \nabla \mathbf{u} = -\nabla p.\end{align}$$
When a small perturbation, $\epsilon$, happens in a fluid at rest, i.e.
$$\begin{align} \rho &= \rho_0 + \epsilon \tilde{\rho}, \\ p &= p_0 + \epsilon \tilde{p}, \\ \mathbf{u} &= \epsilon \tilde{\mathbf{u}}, \end{align}$$
the previous equations are
$$\begin{align} & \epsilon\left(\frac{\partial\tilde{\rho}}{\partial t} + \rho_0 \nabla \cdot \tilde{\mathbf{u}}\right) + \epsilon^2\nabla\cdot\left(\tilde{\rho}\tilde{\mathbf{u}}\right) = 0, \\ & \epsilon\left(\rho_0 \frac{\partial \tilde{\mathbf{u}}}{\partial t} + \nabla \tilde{p}\right) + \epsilon^2\rho_0\tilde{\mathbf{u}}\nabla\cdot\tilde{\mathbf{u}} + \epsilon^3\tilde{\rho}\tilde{\mathbf{u}}\nabla\cdot\tilde{\mathbf{u}} = \mathbf{0}. \end{align}$$
On the other hand, the perturbed pressure can be written in terms of the perturbed density as
$$\tilde{p} = \left(\frac{\partial\tilde{p}}{\partial\tilde{\rho}}\right)_s\tilde{\rho} = c^2\tilde{\rho}.$$
Dropping the higher-order terms because contains the products of two small quantities: $\epsilon^2$ and $\epsilon^3$, and plugging $\tilde{p} = c^2\tilde{\rho}$ into the momentum, the Euler equations become
$$\begin{align} & \frac{\partial\tilde{\rho}}{\partial t} + \rho_0 \nabla \cdot \tilde{\mathbf{u}} = 0, \\ & \rho_0 \frac{\partial \tilde{\mathbf{u}}}{\partial t} + c^2\nabla \tilde{\rho} = \mathbf{0}. \end{align}$$
Applying $\nabla\cdot(\text{momentum eqn.})$, $\nabla(\text{continuity eqn.})$ with $\nabla\times\tilde{\mathbf{u}} = \mathbf{0}$ and linking $\nabla\cdot\tilde{\mathbf{u}}$, $\nabla\tilde{\rho}$ with $\partial\tilde{\rho}/\partial t$ and $\partial\tilde{\mathbf{u}}/\partial t$ via momentum and continuity respectively; the wave equations are given by
$$\begin{align} & \frac{\partial^2\tilde{\rho}}{\partial t^2} - c^2\nabla^2\tilde{\rho} = 0, \\ & \frac{\partial^2\tilde{\mathbf{u}}}{\partial t^2} - c^2\nabla^2\tilde{\mathbf{u}} = \mathbf{0}. \end{align}$$