Edit 2024: I now think that this answer is wrong, specifically that the result in the last paragraph does not answer the original question. I am reluctant to delete this answer as it would also delete a helpful comment of Blass. I may update this answer in the future, however the question looks much more difficult when reading it correctly.
Fortunately I am not completely empty-handed: on p. 20 of Carlson's "Elementary Patterns of Resemblance" (Annals of Pure and Applied Logic vol. 108, 2001) there is a remark that gives an upper bound to this question with $Lan$ restricted to $\{R_0,R_1\}$ only, namely the proof-theoretic ordinal of $\Pi^1_1\mathrm{-CA}_0$.
There is a $\lambda<\omega_1$ such that $L_\lambda\prec L_{\omega_1}$, this can be obtained by taking the least ordinal not in $\textrm{Hull}^{L_{\omega_1}}(\{\varnothing\})$. The hull is already transitive (according to Marek and Srebrny's "Gaps in the Constructible Universe", or with a proof by Andreas Blass in the comments of this answer), so no Mostowski collapse is needed to put it in the form $L_\lambda$. Such $\lambda$ are unbounded in $\omega_1$: for any given $\xi<\omega_1$, by taking $\textrm{Hull}^{L_{\omega_1}}(\xi\cup\{\xi\})$ instead, a $\lambda_\xi>\xi$ can be produced such that $L_{\lambda_\xi}\prec L_{\omega_1}$.
Then, the ordinals $\alpha<\omega_1$ such that there is a $\beta<\alpha$ with $L_\beta\prec L_\alpha$ are unbounded in $\omega_1$. In particular, if $\beta,\alpha<\omega_1$ are such that $L_\beta\prec L_{\omega_1}$, $L_\alpha\prec L_{\omega_1}$, and $\beta<\alpha$, then $L_\beta\prec L_\alpha$. (This may be shown routinely by passing $\phi(\vec a)$ between $L_\beta$, $L_{\omega_1}$, and $L_\alpha$, with $\vec a$ a sequence of parameters from $L_\beta$.) This shows unboundedness since if some $\lambda_\xi$ is chosen for $\beta$, $\lambda_{\lambda_\xi}$ may be chosen for $\alpha$.
Since $\omega_1$ has cofinality $\omega_1$, this unbounded subset of $\omega_1$ must have order type $\omega_1$. Consider the finite $Lan$-model $\{\beta,\alpha\}$, where $\beta,\alpha$ are as in the last paragraph. $\beta R_n\alpha$ holds for all $n\in\mathbb N$, so to get a monomorphism to $M$ there would need to be a two-element subset $\{\gamma,\delta\}$ of $\omega_1$ such that $\gamma R_n\delta$ holds for all $n\in\mathbb N$. Taking $\gamma=\lambda_0$ and $\delta=\lambda_{\lambda_0}$, we get that any $\{\alpha,\beta\}$ is such a finite $Lan$-model. As such $\beta$ are unbounded in $\omega_1$, the order type of $S$ is $\omega_1$.
