  We study the time complexity of the discrete $k$-center problem and related
(exact) geometric set cover problems when $k$ or the size of the cover is
small. We obtain a plethora of new results:
  - We give the first subquadratic algorithm for rectilinear discrete 3-center
in 2D, running in $\widetilde{O}(n^{3/2})$ time.
  - We prove a lower bound of $\Omega(n^{4/3-\delta})$ for rectilinear discrete
3-center in 4D, for any constant $\delta>0$, under a standard hypothesis about
triangle detection in sparse graphs.
  - Given $n$ points and $n$ weighted axis-aligned unit squares in 2D, we give
the first subquadratic algorithm for finding a minimum-weight cover of the
points by 3 unit squares, running in $\widetilde{O}(n^{8/5})$ time. We also
prove a lower bound of $\Omega(n^{3/2-\delta})$ for the same problem in 2D,
under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in
2D, our upper bound is $\widetilde{O}(n^{7/4})$.
  - We prove a lower bound of $\Omega(n^{2-\delta})$ for Euclidean discrete
2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly
matches the straightforward upper bound of $\widetilde{O}(n^\omega)$, if the
matrix multiplication exponent $\omega$ is equal to 2.
  - We similarly prove an $\Omega(n^{k-\delta})$ lower bound for Euclidean
discrete $k$-center in $O(k)$ dimensions for any constant $k\ge 3$, under the
Hyperclique Hypothesis. This lower bound again nearly matches known upper
bounds if $\omega=2$.
  - We also prove an $\Omega(n^{2-\delta})$ lower bound for the problem of
finding 2 boxes to cover the largest number of points, given $n$ points and $n$
boxes in 12D. This matches the straightforward near-quadratic upper bound.
