Least Common Non-Divisor Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$.

Denote $n = |S|$ and $C = \max(S) $.
Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$.  We have an upper bound

$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$

Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.

The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.

In detail, the algorithm consists of two parts:  


Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$
This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory.  (Where does this come from?  For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.


I have two questions that I'm interested in:  


Is there a faster algorithm to solve the problem?
For given $n$ and $C$, how can we construct a set $S$ with maximal least common non-divisor?
It is possible to improve on your second algorithm by using better algorithms for integer factorization.

There are two algorithms for integer factorization that are relevant here:


GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).


Here $L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$.

That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned.  In particular, $L_C[0.33,1.92]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$.  Also $L_{n \log C}[0.5,1.41]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.

So, the total running time for this method is roughly $\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$, and this is asymptotically better than your first method and asymptotically better than your second method.  I don't know if it is possible to do even better.