By the Chinese remainder theorem, we have that:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$
From this, we should be able to write:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$
Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.
We can then write all the quantities you talk about in terms of the generators $g_q, g_p$.
Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$.
Then your equation:
$$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$
Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$.
You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure.
If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$.
I believe we can read off the length of any cycle fairly easily.
In particular, a cycle is a path from $(0,0)$ in $\mathbb{Z}^2$ to $(k_q, k_p)$ such that $k_q\equiv ry_q-z_q\bmod (q-1)$ and $k_p\equiv ry_pz_p\bmod(p-1)$.
The length of the shortest path from $(0,0)$ to $(k_q, k_p)$ is therefore $|k_q| + |k_p|$, which is the length of your cycle.
As $k_q\equiv 0\bmod(q-1)$ (and similarly for $k_p$), we see that the length of any cycle must be of the form $|a_p|(p-1) + |a_q|(q-1)$ for non-zero integers $a_p, a_q$, which puts some restrictions on which possible lengths are achievable (this is related to the Frobenius coin problem). There are likely upper bounds on $a_p$ and $a_q$ which come from the group relations of the type $g_q^{q-1}$, but this requires defining a good notion of "trivial" cycle first.
As for the computability of this, it can be efficiently computed if you know the factorization of $N = pq$ (all of the discussion above does this), and (likely) can't without this. I don't know if there are any gains to rewriting RSA in this way (I don't see any immediately), and don't guarantee the computations above are correct, but they seem vaguely right to me at least.
One thing to worry about is compact representation of the edges. All of the above required knowing the factorization of $N$. If we remove this, then we can abstractly view the cayley graph will as a graph on $\phi(N)$ vertices, which as $p,q\approx 2^{n/2}$ will be $\phi(N)\approx 2^n$.
Vertices can be communicated by indexing into $[\phi(N)]$, and since the graph is 4-regular (I think, edges from each vertex being $\{g_p, g_p^{-1}, g_q, g_q^{-1}\})$ each particular edge can be efficiently described. But I don't know how you can efficiently transmit the entire graph, as there are $O(2^n)$ edges, meaning that treating it as an abstract graph means you cannot efficiently communicate it.
Of course there are efficient ways to "compress" the graph (this must implicitly be done in traditional RSA-based cryptosystems), but its unclear how much of that compression will generalize to other groups, which appears to be your intention.
