Linnik's problem for multiplicative functions

We study a multiplicative function analogue of Linnik’s problem on the least prime in an arithmetic progression. Let $h\text{\hspace{0.17em}⁣}:\mathbb{N}\to \mathbb{R}\setminus \{0\}$ be a multiplicative function, and let $a(\mathrm{m}\mathrm{o}\mathrm{d}q)$ be a reduced residue class. We ask how far one must go before finding square-free integers $n_1,n_2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}q)$ with $h(n_1)<0<h(n_2)$. We show that one can always find such integers with $n_1,n_2\le q^{2+o(1)}$, unless the sign of $h$ strongly pretends to be a real Dirichlet character modulo $q$. Thus, apart from this natural character obstruction, sign changes of a multiplicative function occur in every reduced residue class at a scale corresponding essentially to the square root barrier. In the special case of the Liouville function $\lambda$ this improves on a recent result of Ford and Radziwiłł and matches, up to $q^{o(1)}$ factors, what was previously known conditionally under the generalized Riemann hypothesis.