Are there distribution properties which are "maximally" hard to test?
Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea.

First, it looks like you performed your Chernoff bound with some slightly odd setting of parameters. Note that to perform your suggested "testing by learning" approach, it is sufficient to learn the distribution in total variation distance (or $\ell_1$, if you prefer, which is the same up to a factor 2) to distance $\frac{\varepsilon}{2}$. (before checking "offline" if there is any distribution $p'$ having the property $\mathcal{P}_n$ which itself is at distance at most $\frac{\varepsilon}{2}$ from your learnt hypothesis $\hat{p}$). This would naively lead to an $O\big(\frac{n\log n}{\varepsilon^2}\big)$ sample complexity upper bound for this approach; however, it is known (and "folklore") that learning an arbitrary distribution over a domain of size $n$ up to distance $\varepsilon$ (in total variation distance) can be done with only $O(\frac{n}{\varepsilon^2})$ samples (and this is tight).

So the baseline should actually be $O(\frac{n}{\varepsilon^2})$, which is already linear in $n$. Now, one can ask the next question -- are there "natural" properties for which testing (say, for constant $\varepsilon$) requires a linear dependence in the domain size $n$?

The answer is (as far as I know) "not quite, but close." Namely, following a significant line of work on estimating properties of distributions (or equivalently, tolerant property testing), the results of Valiant and Valiant imply (STOCS'11, FOCS'11, and some others) that the rather contrived property "being $1/10$-close to uniform" has sample complexity $\Theta_\varepsilon(\frac{n}{\log n})$.

(Note that it's a bit "cheating," in the sense that the property is simply a way to take a tolerant testing question and relabel it as testing of an ad hoc property).

If that is not entirely sufficient to quench your thirst, one can also show that for the (natural?) property of "being a $k$-histogram" (is the distribution piecewise constant on a set of $k$ unknown intervals?), setting $k=n/10$ for instance also results in an $\Omega(\frac{n}{\log n})$ lower bound (it's in a paper of mine from 2016; the lower bound follows from a rather simple reduction to the Valiants' result). Now, whether you consider "being an $\frac{n}{100}$-histogram" to be a natural property is up to you.