Let $S(r)$ be the surface of the origin-centered sphere in $\mathbb{R}^3$.
A point is an *integer point* if all its coordinates are integers.

What is the smallest radius $r_n$ such that $S(r_n)$ includes $\ge n$ integer points?

What is the growth rate of $r_n$ with respect to $n$? Is there an algorithm that could compute $r_n$ for a specific given $n$?

It is known that rational points (all coordinates rational) are dense on $S(1)$: see, e.g., the MO question Rational points on a sphere in $\mathbb{R}^d$.

One possible approach is via rational points of bounded height. The height of a rational $a/b$ in lowest terms is max$(|a|,|b|)$, and the height of a rational point is the max of the heights of its coordinates.

^{ Rationals of height $\le 2048$ on sphere. Image due to Stefan Kohl in this answer. }

Choose an appropriate $h_\max$, perhaps using an estimate of the number of rational points of height at most $h_\max$ on $S(1)$. Then scale all coordinates by the LCM of the points' denominators. For example, for $h_\max=10$, scaling by $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ would suffice to clear all denominators, so that $S(2520)$ includes all those points at integer coordinates.

But this would not necessarily result in the minimum $r_n$ for a given $n$. It would likely be better to use rational points that result in a small LCM.

Exact calculations on a sphere (for example, computing Voronoi diagrams on a sphere) often need integer points of bounded size.

**Update**. The exact answer to the question in the title, due to Dap and Gerhard Paseman, is that a sphere of radius $\sqrt{74} \approx 8.6$ includes $120$ integer points on its surface, and smaller spheres include fewer than $100$ points.

1more comment