Pollard's Rho - Constructing the Random Function
If you generate group elements at random as you suggest then you can indeed invoke the "Birthday Paradox" to find logarithms in time $O(\sqrt p)$. Unfortunately your storage requirements are the same and for cryptographically interesting group orders your method is therefore far from optimal.

The fastest way for groups with (apparently) no exploitable structure (like elliptic curves) uses "distinguished points" as it allows you to tailor your parameters to suit the storage you have available. Then there are issues relating to whether you're just finding one discrete logarithm or many.

Having said that, I believe that pretty well any reasonable random number generator will be satisfactory for your method. If a particular method of generating random numbers had a performance consistently different from normal then that would probably be of independent mathematical interest, worthy of publication.