How to quickly find a few bisimulations on a given labelled digraph?
You can always return the bisimulation $∅$ in constant time.

You are right about the fact that in order to return $R$, you will have at least some sanity checks.

For example you could think that returning all bisimulations of the form $\{(p,q)\}$ when $p$ and $q$ have the same label and such that $p\not→$ and $q\not→$ is easy, but not that much: you need to proceed through $O(m+n)$ time and $O(n)$ space! (Or $O(mn^2)$ time and $O(1)$ space (not counting the output)). Checking that a small relation is a bisimulation is not a lot easier than finding the relation $\sim$.

The computation of $\sim$ uses clever properties specific to $\sim$ and fusing states tricks. These techniques would not be useful for several relations and doing better than $O(m\log n)$ (not loglinear) is hard. Also, computing "a few" bisimulation is of arguable interest.

Another thing: deciding if $p\sim q$ implies computing the relation $\sim$ on the union of the directed graphs $G_p=\{x ∣ p \stackrel{a_1\dots a_n}{\longrightarrow}x\}$ and $G_q=\{x ∣ q \stackrel{b_1\dots b_m}{\longrightarrow}x\}$ which can be a significant part of the graph. If however you know have information like the size of $G_p$ and $G_q$ then you can compute $\sim$ on smaller graphs. Keep in mind that algorithms with Tarjan in their name tend to have very tight bounds. This is not an exception.