Efficiency of finding sub group order vs factorization
Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden $r$, but it simplifies the presentation].

To further simplify, let's also assume that $s$ contains no constant term. In this setting, each pair $(a_i,b_i)$ as in the question is equivalent to a pair $(A_i,b_i)$ together with the information that $s(b_i)\equiv A_i\pmod{q_0}$. This can be easily rewritten as a linear equation $$\sum_{k=1}^{\ell}s_kb_i^k\equiv A_i\pmod{q_0},$$where $\ell$ is the degree of $s$. Collect $\ell+1$ such equations and form the matrix:
$$
M=\left(\begin{array}{ccccc}-A_1 &amp;b_1 &amp; b_1^2 &amp; \cdots &amp;b_1^\ell\\
-A_2 &amp; b_2 &amp; b_2^2 &amp; \cdots &amp;b_2^\ell\\
\vdots &amp;\vdots &amp; \vdots &amp; \ddots &amp; \vdots\\
-A_{\ell+1}&amp; b_{\ell+1} &amp; b_{\ell+1}^2 &amp; \cdots &amp;b_{\ell+1}^\ell\\
\end{array}\right).
$$ 
By construction the system $Mx=0$ has a non zero solution vector (formed by a '1' followed by the coefficients of $s$) modulo $q_0$. As a consequence, $\det(M)$ is a multiple of $q_0$. Form two such matrices, take gcd and you can recover $q_0$ directly.

Note that this can be made more efficient by taking a rectangular matrix $M$ (with extra equations) and computing a Hermite normal form.