Let $D$ be the disk bounded by the radius minimizing circle $\partial D = C\{{x_1, \dots, x_n\}}$. Two outcomes, $p \in D$ or $p \notin D$.
If $p \notin C\{x_1, \dots, x_n, p\}$ then $p$ is inside the disk $D$ bounded by $C\{{x_1, \dots, x_n\}}$. But we assumed $p \notin D$.
This is an instance of the problem of Appolonius. By induction, we are looking for the smallest circle $C_1 = C\{x_1, \dots, x_n, p\}$ which contains $p$ and $C_0 = C\{{x_1, \dots, x_n\}}$.
If $p$ is not inside $C_0$, then $C_1$ should be tangent $C_0$ and go through $p$. For this case of the Appolonius problem, you actually need two points to specify a unique circle.
In other words, there are infinitely circles $C_1$ passing through $p$ and tangent to $C_0$. One of these has the smallest radius.
The above is not quite true... instead of $C_1$ being tangent to $C_0$ and $p$, just $C_1$ goes through $p$ and its tangent to the convex hull, $\overline{\{x_1, \dots, x_n \}}$.
Lemma The diameter of the minimal circle is the same as the diameter of the convex hull
The minimizing circle cuts through at least three points in the set. Generically, exactly 3.
The circle needs surround all the points so the diameter is at least that of the convex hull, but it can be bigger. If the min circle didn't go through any points, we could shrink the radius so it passes through at least one. In fact, since 3 points determine a circle, we can shrink the radius until it passes through at least 3. Generically, there shouldn't be a fourth point exactly on the circle.
So we can run through all $\binom{n}{3}$ triples of points, verify the circumcircle contains all the other points, and find the one with the smallest radius. For the induction, we adjoin $p$ and iterate through the $\binom{n+1}{3}$ points.
I found graphic in a graduate Computer Science course, on the "Minimal Enclosing Circle" problem. Wikipedia calls this the "Smallest Circle Problem" and attributes it to Mathematician James Joseph Sylvester. This question was also asked on the StackOverflow programming site:
It was a computer science homework for sophomores at Princeton (Cos 226)
Literature points to a fast solution by Emo Welzl. The paper is called Smallest Enclosing Disks (Balls and Ellipsoids)
Proposition the radius minimizing circle is unique
For contradiction, if we have two circles $C, C'$ which contain all $n$ points, these points must lie in the intersection of the two circles $C \cap C'$. The intersection of these two circles is a lens shape with diameter smaller than that of $C$ or $C'$.
This diameter determines a circle still containing all $n$ points, but with diameter smaller than that of $C$ or $C'$.
Best Answer
Your idea is good, and you just need to find the simplest rigorous way forward. One way is as follows: Take any ray $L$ with $2018$ points on its left. (I leave you to figure out how to rigorously prove the existence of such $L$.) Let $P$ be a point on $L$. Let $C(k)$ be the circle on the left of $L$ that is tangent to $L$ at $P$. Clearly $C(k+1)$ encircles at least as many points in $E$ as $C(k)$. But $E$ is finite, so $C(k)$ can only increase finitely many times as $k$ increases. Thus $C(m)$ for some $m$ encircles all the points in $E$.