I know that there exist many proofs that show $cos(x)$ is uniformly continous that rely on Lipschitz continuity and/or the mean value theorem. However, how can I show that $cos(x)$ is continuous in the first place? The mean value theorem requires that the function be differentiable (hence continuous) in the first place so I can't really use it without proving continuity.
Use the unit circle. Suppose $0< x < \pi/2$. Then if you progress clockwise on the unit circle distance $x,$ you arrive at the point $(\cos(x), \sin(x))$.
The shortest distance to the origin from this point is $\sin(x)$. That is shorter than the distance traveling along the unit circle, which is $x$. We therefore know $$\sin(x) < x, \qquad 0 < x <\pi/2.$$
You should be able to use the properties of sine and cosine to get to your general result.