How to construct a good PRF from a block cipher?
What you're looking for is often called a construction of a PRF with "beyond the birthday bound security," and you can probably find some constructions by searching on variants of that term.

For concreteness, this paper by Iwata (alternate link) almost gives a solution to your problem: The only deficiencies are that the resulting $F$ has inputs one bit narrower than $E$, and it does not achieve your definition of security for every $\varepsilon &gt; 0$.  Specializing that construction down to your setting, and using your notation, it defines $F(x)$ for $x\in\{0,1\}^{b-1}$ as $$F(x) = E(x\|0)\oplus E(x\|1),$$
where $\|$ denotes concatenation.  Its proof applies for a number queries well beyond $2^{b/2}$, which is obviously non-trivially better than the direct $F(x) = E(x)$ construction.