This is really an extended comment.

I think that it's unlikely that an unconditional result of this type is known, because your problem is not all that different from the problem of finding a prime in the desired interval. For fixed $c$, the number of positive integers less than or equal to $x^c$ with no prime factor less than $x$ is asymptotic to $$c\cdot\omega(c){x \over \log x}$$ where $\omega$ is the Buchstab function. In other words the density of the numbers you're interested in is only larger than the density of primes by a constant factor, so it would be rather surprising to me if one of them could be found much more efficiently than a prime could be. Of course this is not a proof and one could imagine a "formula" such as $n!+1$ that always yields a composite, but this seems a bit too much to hope for.

Also I'm not sure I understand your suggested weakening of the upper bound to $q < n^{O(n^\epsilon)}$. If $q$ is that large, then it takes something like $n^\epsilon \log n$ bits just to write it down, and that can't be done in polylog time. I suppose you could allow $q$ to be expressed using some "formula" that is more compact than binary representation, but in that case, very few numbers of that size are going to be expressible by a short formula.

This is really an extended comment.

I think that it's unlikely that an unconditional result of this type is known, because your problem is not all that different from the problem of finding a prime in the desired interval. For fixed $c$, the number of positive integers less than or equal to $x^c$ with no prime factor less than $x$ is asymptotic to $$c\cdot\omega(c){x \over \log x}$$ where $\omega$ is the Buchstab function. In other words the density of the numbers you're interested in is only larger than the density of primes by a constant factor, so it would be rather surprising to me if one of them could be found much more efficiently than a prime could be. Of course this is not a proof and one could imagine that suitable weakenings of the standard conjectures have been proved unconditionally, but again I would be rather surprised if that were true.

Also I'm not sure I understand your suggested weakening of the upper bound to $q < n^{O(n^\epsilon)}$. If $q$ is that large, then it takes something like $n^\epsilon \log n$ bits just to write it down, and that can't be done in polylog time. I suppose you could allow $q$ to be expressed using some "formula" that is more compact than binary representation, but in that case, very few numbers of that size are going to be expressible by a short formula.