This is a classical problem in Linear Programming - to start a simplex method, one must find a vertex.
This is so-called "Phase I" of the simplex method, and without doubt the best ways to do this have been researched a lot. See e.g. what Brian Borchers wrote in scicomp, "How to start the Simplex method from a feasible internal point?"
It is not hard to show that $O(mn^2)$ operations suffice. Basically, it's some kind of extended Gauss elimination. Assume that we already have $k$ independent facets with $x_k$ on them, given by a triangularised matrix of the corresponding equations, and the remaining inequalities are also transformed so that the 1st $k\geq 0$ variables do not arise in them.
Now, fix the $k+2$-th, $k+3$-th,... $n$-th coordinate of $x$ to be as in $x_k$, obtaining a univariate system of inequalities -- $k+1$-th coordinate is the variable. It specifies a finite range $[\tau,\tau']$. Set the $k+1$-th coordinate of $x_{k+1}$ to be equal to either $\tau$ or $\tau'$, and the $k+2$-th,... $n$-th coordinates of $x_{k+1}$ to be the same as in $x_k$. Use the triangular system of equations to back-solve for $k$-th, $k-1$-th,...,1st coordinates of $x_{k+1}$. (This is all quick, needs $O(nm)$).
Now we have $x_{k+1}$, lying in a face of smaller dimension that $x_k$; at this point one has to triangularise the newly found equations; if the dimension of the face drops by $r$, one needs at most $O(rnm)$ operations. At this point we are ready to repeat the loop, with $k$ increased by $r$.