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$.
If $d$ divides both $a$ and $b$, then $d$ divides their sum. By similar reasoning, the max gcd must be a divisor of $315 = 5 \times 7 \times 3^2.$
Further, set $d$ as the gcd. Then, you must have that
$a_1, a_2, \cdots, a_7$ can be represented by
$(d \times x_1), (d \times x_2), \cdots, (d \times x_7).$
This implies that $x_1, \cdots, x_7$ must be distinct positive integers, such that
$\displaystyle x_1 + x_2 + \cdots + x_7 = \frac{315}{d}$.
Further, just as you are very limited in your choices for $d$, a factor of $315$, you are similarly limited in your choices for $~\displaystyle \frac{315}{d}.$
Trying to maximize $d$ is equivalent to trying to minimize $~\displaystyle \frac{315}{d}.$
This implies that you are trying to minimize $x_1 + x_2 + \cdots + x_7.$
However, since $x_1, \cdots, x_7$ must all be positive integers, their sum must be $\geq 1 + 2 + \cdots + 7 = 28.$
Then, you want $~\displaystyle \frac{315}{d}$ to be as small as possible, and still be $\geq 28.$
With $315$ being factored by $5 \times 7 \times 3^2,$ it is immediate that $\displaystyle \frac{315}{d}$ can not be an element in $\{28,29,\cdots, 34\}.$
Therefore, $~\displaystyle \frac{315}{d}$ is minimized by setting it to $(35)$. This implies that $d = 9$, so $(9)$ is the largest possible gcd.
It remains to verify that the equation $x_1 + x_2 + \cdots + x_7 = 35$
does have a solution in distinct positive integers.
Since there is the obvious solution of $(x_1, x_2, \cdots, x_6, x_7) = (1,2,\cdots, 6, 14)$, the problem is solved.
Best Answer
We can prove that the following algorithm returns a solution with product $n^{k-o(1)}$:
For each value of $v = \frac{a_i}{\gcd(a_i, m)}$, at most $d(m)$ different $a_i$'s could have produced it, one for each possible result $\gcd(a_i, m)$. Because all $a_i$'s are distinct, this shows that the maximum value is at least $\frac{n}{d(m)}$. But $m \leq n^k$, and according to the divisor bound $d(n) = n^{o(1)}$, so the maximum value at each step is at least $n^{1-k\cdot o(1)}$, and so the product after all $k$ steps is at least $n^{k - k^2 o(1)}$ and when $k$ is constant this is $n^{k - o(1)}$.
Using a more precise form of the divisor bound one can see that the $o(1)$ term is actually $O(\frac{1}{\log\log n})$, while the conjecture wants a term of $O(\frac{1}{\log n})$, so this doesn't prove it.