As noted in the OP edit, we need to take $\epsilon > 1$ odd as at least one of $1+L$, $2+3L$ is always even.
Suppose $p$ is a prime divisor of $(u+Lm, v+Ln)$. Then it also divides the integer combination $n(u+Lm)-m(v+Ln) = nu - mv$, which is a constant independent of $L$.
So the only possible primes dividing the gcd are the divisors of $nu-mv$. Note that the constraints preclude this quantity from being zero (otherwise $n/v = m/u$ with both fractions being in lowest terms, which contradicts $m\ne n$), so there are only finitely many such primes. Likewise there are only finitely many primes dividing $\epsilon$. Let $P$ be the largest of all primes in either category.
By the argument of the related question, for any prime $p\ge 3$, we can choose a congruence class for $L$ mod $p$ such that $p \nmid m+Lu$ and $p \nmid n + Lv$. For $p=2$, we can’t guarantee the same, but we can at least ensure one of $m+Lu$ and $n+Lv$ is odd by fixing the parity of $L$.
Combining all these congruences for all primes $p\le P$, we get a congruence class for $L$ (modulo the primorial of $P$) which ensures $(m+Lu, n+Lv) = 1$ (recall that primes above $P$ can’t divide the gcd), as well as the $\epsilon$ condition.
I feel there is probably a more efficient construction based on a similar question I have seen years before. Maybe someone can provide it.
This answer completes rtybase's answer, which finished off with
- if $\color{red}{\gcd(a_i,a_j)=d}>1$ and $p\mid d$ then ...
However, note $i$ and $j$ will be used as general indices here instead of the specific ones mentioned in the other answer. Also, assume the sequence values are sorted into increasing order, for simpler handling. First, here are $2$ lemmas I will use later.
Lemma #$1$:
If there's any factor $e \gt 1$ where $e \mid a_i$ for all $1 \le i \le p + 1$, then $e \mid d = \gcd(a_i,a_j)$ so, with $j \gt i$, the fraction $\frac{a_j}{d}$ would be the same as if $e$ was divided from both $a_i$ and $a_j$. As such, the maximum fraction value would be the same as if $e$ was first divided from all $a_i$. Note that related proofs about moving out a common factor among GCD elements are given at Prove that $(ma, mb) = |m|(a, b)\ $ [GCD Distributive Law].
Lemma #$2$:
For any sub-sequence of $t \ge 1$ integers, i.e., $a_{b_i}$ for increasing indices $b_i$ with $1 \le i \le t$, we have $L = \operatorname{lcm}(a_{b_1},a_{b_2},\ldots,a_{b_t}) \ge ta_{b_1}$. Consider the strictly decreasing sequence $\frac{L}{a_{b_i}}$ for $1 \le i \le t$. With each value being a positive integer, the largest (i.e., first) one must be $\ge t$. Thus, $\frac{L}{a_{b_1}} \ge t \;\to\; L \ge ta_{b_1}$. Note similar proofs for this are given at LCM of list of strictly increasing positive integers, and in the AoPS thread number theory.
Use lemma #$1$ to divide by any common factor among all the $a_i$, so there's no factor $\gt 1$ in common among all the $a_i$. After doing this, if $p \mid d = \gcd(a_i,a_j)$ for some distinct $i$ and $j$, then there are
$$2 \le f \le p \tag{1}\label{eq1A}$$
sequence values which are a multiple of $p$ (note it's not all of them, i.e., $p + 1$, as discussed just above). Consider the indices of these values to be $g_i$, so we get for some integers $h_i$ that
$$a_{g_i} = h_i(p), \; 1 \le i \le f \tag{2}\label{eq2A}$$
Among the remaining
$$m = (p + 1) - f \tag{3}\label{eq3A}$$
sequence values which have no factor of $p$, if for any one of them, say $a_n$, for some $1 \le i \le f$ we have $\gcd(a_{g_i},a_n) = q \lt h_i$, then $\frac{a_{g_i}}{q} \ge 2p \gt p + 1$. If $a_n \gt a_{g_i}$, then $\frac{a_{n}}{q}$ would be even larger. In either case, we have a ratio $\ge p + 1$.
Otherwise, for all $n$ where $p \nmid a_n$, we have
$$\gcd(a_n,a_i)=h_i \;\;\forall\;\; 1 \le i \le f \tag{4}\label{eq4A}$$
Then, with $r = \operatorname{lcm}(h_1,h_2,\ldots,h_f)$, we get as shown in lemma #$2$ that
$$r \ge f(h_1) \tag{5}\label{eq5A}$$
Also, we must have $r$ dividing all of those $m$ sequence values with no factor of $p$. As such, the largest of these $m$ values, say $a_u$, has
$$a_u \ge mr \tag{6}\label{eq6A}$$
From \eqref{eq5A}, this means
$$a_u \ge mf(h_1) \;\;\to\;\; \frac{a_u}{h_1} \ge mf \tag{7}\label{eq7A}$$
Using \eqref{eq3A}, we get
$$mf = ((p + 1) - f)f = (p + 1)f - f^2 \tag{8}\label{eq8A}$$
If \eqref{eq8A} is $\ge p$, then because it's a lower bound in \eqref{eq7A}, it means we're finished. This is because, by using \eqref{eq2A}, with a lower bound of $p$ (i.e., for $f=p$), we have $\frac{a_u}{h_1} = p \;\to\; a_u = ph_1 = a_{g_1}$. However, since $u \neq g_1$, this contradicts the requirement the integers are all distinct, so this possibility is not valid. Thus, $\frac{a_u}{h_1}$ will have to be at least $p+1$ anyway. We can therefore use $i=g_1$ and $j=u$ because, from \eqref{eq2A} and \eqref{eq4A}, we have $h_1 = \gcd(a_u, a_{g_1})$.
For $2 \le f \le p - 1$, note that \eqref{eq8A} is always $\ge p + 1$. This can easily be shown since, if we let $w(x) = (p + 1)x - x^2$, then $w(x) = w(p + 1 - x)$, with $w(2) = w(p - 1) = 2p - 2$. Also, $w'(x) = p + 1 - 2x \ge 0 \implies x \le \frac{p + 1}{2}$. In other words, $w(x)$ increases up to $x = \frac{p + 1}{2}$ and then decreases symmetrically.
In summary, this handles all the remaining cases not covered by rtbyase's answer to prove the original requested problem always holds, i.e., there exist at least $2$ sequence values such that the ratio of the larger value to their $\gcd$ is always at least $p + 1$.
Best Answer
In practice it is not that hard to check (2). Unless $b$ is itself divisible by $p$, there is exactly one congruence class of $m$ for which $a+bm$ is divisible by $p$. That means that in the generically-worst case, there are at most $k$ congruence classes of $m$ mod $p$ that could cause any of the $\{f_j(m)\}_j$ to be divisible by $p$.
If $p > k$ then there will always be some congruence class available that makes all the $\{f_j(m)\}$ non-zero, so we only need to be concerned with $p \le k$, at least when $p$ does not divide any $b_j$.
But there are only finitely many possible primes that divide any $b_j$, so those can be checked separately (as metamorphy's answer suggests, they are in fact completely harmless unless $p$ also divides $a_j$).