Existence of a proper Morse function
I will write a very fancy and unnecessarily complicated proof. However, it is my expectation that this proof will be illuminating. Similar ideas are used in other contexts, such as Morse theory on infinite-dimensional manifolds. Instead of your finite-dimensional space of functions coming from the dot product, I will construct an infinite-dimensional space of functions which covers every way you might think of perturbing $f$.
For every point $x \in M$, pick a chart $(U_x, \varphi_x)$ with $\varphi_x(x) = 0 \in \Bbb R^n$ so that $f(U_x) \subset (f(x) - \delta, f(x) + \delta)$ for a predetermined uniform constant $\delta$, and pick a bump function $\rho$ supported in the unit ball of $\Bbb R^n$ and the identity near zero. For every $v \in T_0 \Bbb R^n$, define $$g_{x,v}(p) = \rho\left(\varphi_x(p)\right) \left(\varphi_x(p) \cdot v\right),$$ where the dot means the dot product. This function has $(dg_{x,v})_x(w) = d\varphi_x(w) \cdot v$. In particular, as $v$ varies, we see that the $(dg_{x,v})_x$ runs through the space of all functionals on $T_x M$.
Pick a countable set $(x_i, v_i)$ which is dense in $TM$. Let $C_n = \sum \|g_{x_i, v_i}\|_{C^n} + 2^n.$ Write $\mathcal P = \ell^1(C_n)$ for the Banach space whose elements are sequences $(a_1, \cdots)$ such that $\sum C_n |a_i| < \infty$. To each element $\pi = (a_1, \cdots)$ of $\mathcal P$ is associated a function $g_\pi: M \to \Bbb R$, given as $$g_\pi(x) = \sum a_i g_{x_i,v_i}(x).$$
The bounds on the $C^n$ norms imply that $g_\pi$ is smooth (in fact, the map $g: \mathcal P \times M \to \Bbb R$ is smooth), and further each $g_\pi$ is bounded (this comes from $C_n \geq 2^n$). So any $f + g_\pi$ is a proper smooth function.
Now consider the map $F: \mathcal P \times M \to TM$ given by $(\pi, x) \mapsto \nabla(f + g_\pi)$. You can quickly check that this map is transverse to the zero section (essentially because $\mathcal P$ is so big that it makes up all of those directions).
In particular, the "parameterized critical set" $\mathcal C \subset \mathcal P \times M$, given as $F^{-1}(0)$, is a smooth manifold; furthermore, $\mathcal C \cap \{\pi\} \times M$ is the critical set of the function $f + g_\pi$; this critical set is cut out transversely (that is,
Now apply the Sard-Smale theorem to the projection $p: \mathcal C \to \mathcal P$ to find a regular value $\pi$, and hence a smooth proper Morse function $f + g_\pi$.