How long does it take to find a short cycle in a random graph?
No, you can't beat $\Theta(\sqrt{n})$ queries.  I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms.  This is all anticipated in exfret's answer; I am just filling in some of the details.

Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $i$th edge of vertex $v$'s adjacency list" or "test whether vertices $v,w$ are connected by an edge".  We can assume that no query is repeated, as any algorithm that repeats a query can be transformed to one that never repeats any query.  Similarly, we can assume that the algorithm never does a connectivity query on any pair of vertices that are already known to be connected by an edge (namely, testing $v,w$ when $w$ was previously returned by a fetch query on $v$, or $v$ was previously returned by a fetch query on $w$, or we previously tested connectivity of $w,v$).

Let $E_k$ denote the event that, during the first $k$ queries, no vertex $w$ is returned by more than one fetch-query, and no fetch-query returns a vertex that was previously queried, and that no connectivity-test-query returns "connected".  We'll prove that $\Pr[E_q] = 1-o(1)$ if $q=o(\sqrt{n})$.  It follows that no algorithm that makes $o(\sqrt{n})$ queries can have a constant probability of finding a 4-cycle.

How do we prove this?  Let's compute $\Pr[E_k|E_{k-1}]$.  There are two cases: either the $k$th query is a fetch query, or it is an connectivity-test query:


If the $k$th query is a fetch query on vertex $v$, there are $2(k-1)$ vertices mentioned among the first $k-1$ queries, and if the $k$th query returns one of those then we will have $\neg E_k$, otherwise we will have $E_k$.  Now the response to the $k$th query is uniformly distributed on a set $S$ of vertices, where $S$ contains all vertices that haven't been returned by prior fetch queries on $v$, so the response to the $k$th query is uniformly distributed on a set of size at least $n-k+1$.  The probability of hitting at least one of these is $\le 2(k-1)/(n-k+1)$, so in this case, $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$.
If the $k$th query is a connectivity-test query, then $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$.


In either case, if $q=o(\sqrt{n})$ we have

$$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$$

Now,

$$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$$

If $k \le q \le \sqrt{n}$, then

$$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$$

so

$$\Pr[E_q] \ge (1 - {2 q  \over n - q})^q.$$

The right-hand side is approximately $\exp \{ - 2q^2/(n-q)\}$.  When $q = o(\sqrt{n})$, this is $1 -o(1)$.

In conclusion: $\Pr[E_q] = 1-o(1)$ when $q=o(\sqrt{n})$.  It follows that you need $\Omega(\sqrt{n})$ to have constant probability of finding any cycle (let alone a 4-cycle).