I don't know a full answer to this question (which is why I asked it!), but here's what I've been able to determine so far…
Most of the known solutions and partial solutions to the quadratic residuosity problem are based on the prime factors of $m$. In particular, quadratic residuosity is efficient to check for prime $m$, and a number is a quadratic residue modulo $m$ if it's a quadratic residue modulo every prime factor of $m$, so one important criterion is that the factorisation of $m$ is not known by an adversary. As mentioned to the comments in the question, finding semiprimes that are hard to factorise is a well-known problem, given their use in RSA.
When it comes to the decision problem version of quadratic residuosity, there's also an important criterion on the value of $r$: an efficient algorithm (based on the Jacobi symbol) exists to know whether $a$ is a quadratic residue modulo an odd or even number of prime factors of $m$. If an adversary either knows or can guess the number of prime factors of $m$ (e.g. they know that $m$ is likely to be a semiprime), then around half the possible values of $r$ will be efficiently determinable as quadratic non-residues of $m$ (because they need to be a quadratic residue to every prime factor of $m$, and yet the number of prime factors of $m$ that they are quadratic residues to has a different parity). The conclusion is that $r$ must be chosen to be a quadratic non-residue to an even number of prime factors of $m$ (e.g. if $m$ is a semiprime $pq$, then $r$ must be a quadratic residue to either both of $p$ and $q$, or else neither).
$4n+1$ primes and $4n+3$ primes generally interact with quadratic residuosity problems in different ways, so it's possible that there's a security difference between the two different types of prime. (For example, it is of course easy to intentionally generate a quadratic residue $r$ for every prime factor of any given $m$, even without knowing its factorisation, simply by squaring a random $a$; when using the product of two $4n+3$ primes, it's also easy to intentionally generate a quadratic non-residue for every prime factor.) For Blum Blum Shub, a CSPRNG based on the quadratic residuosity problem, there's a requirement to use the product of two $4n+3$ primes as $m$ (and also to keep $\textrm{gcd}(p-1,q-1)$ small). These requirements appear to be specific to the algorithm in question, in order to ensure that the CSPRNG's period is large, and thus might not be required for the problem more generally; however, more effort has likely been put into breaking the quadratic residuosity problem in this case than in cases with no cryptographic applications, so it may make sense to use such values to benefit from the additional scrutiny they may have been given.
It's also, of course, important to avoid trivial cases, e.g. you wouldn't want to pick $r=0$. One highly important case to avoid seems to be $\textrm{gcd}(r,m)\neq 1$ (both because it makes quadratic residuosity easier to directly calculate, and for the more obvious reason that it reveals a factor of $m$). Apart from that, a random $r$ (that's been verified to have the correct Jacobi symbol, i.e. to be a quadratic non-residue of an even number of factors of $m$) will come up at a random point in a brute-force search for quadratic residuosity, so is likely to be secure.
It's probably worth avoiding the smallest values of $a$ because it's possible to, e.g., efficiently search all the values $0\leq a<\sqrt{m}$ in a single calculation, thus the gain from discarding small $a$ is probably larger than the loss from giving a brute-forcing adversary a smaller search space (even if the adversary knows how many values have been discarded, and thus can start their search higher); however, this is something I'm not sure on, and the optimal number of values of $a$ to discard is unclear. Similarly, it may be worth avoiding values $r$ for which $-r=a^2$ for small $a$ (because the quadratic residuosities of $r$ and $-r$ are related).
