Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

I guess I should try and answer that!

I don't really have a good answer to the question of why the random method is not mentioned in the book, and I would agree that it might to be the fastest method if you simply want to compute and store a complete transversal.

I guess the point is that in many applications you want to do something a little different from that, and the two methods described in the book are geared towards two different types of applications.

The first method described allows you to seach through the transversal elements in a well-defined order, without needing to store any of them. You would use that if you were looking for an element with a certain property. It is particularly suitable if the index of the subgroup is large, and storing a complete transversal would cause storage space problems on your computer.

The second method described has larger storage overheads (although you don't need to store the complete permutations in the transversal - the transversal elements can be stored more efficiently in a tree-like structure), but the data structures computed allow you to identify the coset representative of a given group element quickly. Sois this is particularly suitable if you also want to compute the action of the group by multiplication of the cosets of the subgroup, which is a very frequent application. Finding a transversal using random methods might be quicker, but it would not be suitable for this application.

It is also worth mentioning that although these algorithms both involve backtrack searches, in practice the difficulties tend to arise from large output size when the index if big rather than from the backtrack search. In other words, it is $|G:H|$ that is the significant term in the complexity, and so the $|G:H|^2$ factor in the complexity estimate for the random method might make it slower in examples with large index. (In particular, I am very sceptical about your claim that the random method is more efficient for subgroups of order about $\sqrt{|G|}$.)

Interestingly random methods are used a lot in practice when searching for double coset representatives of two subgroups, but in that case they suffer from the problem that the double cosets do not all have the same size, and representatives of the smaller double cosets can be hard to find.