Suppose we restrict to *concave* distributions, i.e. distributions with densities $f$ for which
$$f\left(\frac{a+b}{2}\right) \ge \frac{f(a)+f(b)}{2}$$
for any $a,b\in[0,1]$.

Then there is a simple test on $n$ samples:
- Let $P_1$ be the fraction of samples between $0$ and $\frac14$.
- Let $P_4$ be the fraction of samples between $\frac34$ and $1$.
- If $\min(P_1,P_4) > 1/4-\epsilon/12$, output "uniform"
- If $\min(P_1,P_4) < 1/4-\epsilon/12$, output "non-uniform"

If $n>50/\epsilon^2$, then this test succeeds with probability at least $3/4$ on the uniform distribution, and with probability at least $3/4$ on any concave distribution at total variation distance at least $\epsilon$ from uniform.

The criterion of concavity is broad enough to cover many reasonable distributions that one might compare with the uniform distribution, including the below (illustrated with $\epsilon=1/10$)

[![$1-4\epsilon+8\epsilon x][1]][1]
[![1+4\epsilon-8\epsilon x][2]][2]

[![1-sqrt(27)(6x^2-6x+1)\epsilon][3]][3]
[![min(x/(2\epsilon),(2\epsilon x+2\epsilon-1)/(4\epsilon-1)][4]][4]

We can bound the test's probability of failure for the uniform distribution by
\begin{align}
&2P\left[\ \ B\left(n,\ \ \ \frac{1}{4}\ \ \ \right)<\frac{1}{4}-\frac{n\epsilon}{12}\right] \\
\sim &2P\left[N\left(\frac{n}{4},\frac{\sqrt{3n}}{4}\right)<\frac{n}{4}-\frac{n\epsilon}{12}\right]\\
= &2\,\Phi\left(-\frac{\sqrt{n}\epsilon}{3\sqrt{3}} \right)\\
< &2\,\Phi\left(-\frac{\sqrt{50}}{3\sqrt{3}} \right)\\
= &0.174
\end{align}

To bound the probability of failure for non-uniform distributions, we need to know that either $[0,1/4]$ or $[3/4,1]$ will be substantially less probable than average. 

**Lemma:**
If $f(x)$ is concave and positive on $[0,1]$ with $\int_0^1 f(x)dx = 1$ and
$$\int_0^1 \max(0,1-f(x))\,dx \ge \epsilon$$
then
$$\min\!\left(\int_0^{1/4}f(x)\,dx, \int_{3/4}^1 f(x)\,dx\right) \le \frac14-\frac\epsilon8 $$

If $f$ is the pdf of a distribution, then the first integral is its total variation distance to the uniform distribution; the second and third integrals are the limits of $P_1$ and $P_4$.

I have verified this lemma using Mathematica, and I hope that someone will see a clean proof from some standard properties of concave functions. One can also verify that the examples above satisfy both the hypotheses and the conclusion of the lemma. 

With this lemma, the probability of failure for the non-uniform distributions is bounded by
\begin{align}
&P\left[B\left(n,\frac{1}{4}-\frac{\epsilon}{8}\right)>\frac{n}{4}-\frac{n\epsilon}{12}\right]
\\
\sim &P\left[N\left(
\frac{n}{4}-\frac{n\epsilon}{8},\frac{\sqrt{n(2-\epsilon)(6+\epsilon)}}{8}\right)
>\frac{n}{4}-\frac{n\epsilon}{12}\right]
\\
< &P\left[N\left(
0,\frac{\sqrt{12n}}{8}\right)
>\frac{n\epsilon}{24}\right]
\\
=&1-\Phi\left(\frac{\sqrt{n}\epsilon}{3\sqrt{12}}\right)
\\
<&1-\Phi\left(\frac{\sqrt{50}}{3\sqrt{12}}\right)
\\
=&.248
\\
\end{align}


  [1]: https://i.sstatic.net/POR9Sm.png
  [2]: https://i.sstatic.net/p8i7im.png
  [3]: https://i.sstatic.net/IuNvV.png
  [4]: https://i.sstatic.net/4DrcP.png