Properties of Random Directed Graphs with Fixed Out-Degree
In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$.  I don't remember enough about these proofs to know whether everything goes through in the directed case (certainly some properties are different: the uniform distribution is no longer stationary), but it may be worth looking into.  Good references for expander graphs are Expander Graphs and their Applications by Hoory, Linial, and Wigderson and Pseudorandomness by Vadhan.