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).
