How to construct a good PRF from a block cipher? We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as instantiated in practice by TDEA for $b=64$ or AES-256 for $b=128$, and one fixed random secret key.

I tentatively define a good PRF to be one indistinguishable (with small constant advantage) from a random function, assuming $2^{b(1-\epsilon)}$ queries to an oracle implementing our construction of $F$ from $E$, and delegating invocations of $E$ (edit: and in addition of $E^{-1}$ if that helps) to a random oracle for that. Fix this definition as necessary (Update: I'm told by the answers that for $\epsilon&lt;1/2$, this is roughly what's called a PRF with beyond the birthday bound security).

Are there simple constructions of $F$ from $E$ with a security argument?

$F(x)=E(x)$ is squarely unfit: it can be distinguished from a random function by detecting collisions after $2^{b/2}$ distinct queries, which happens with sizable probability for a random function but not for a random permutation. That can even be done with constant memory, using Floyd's cycle finding. A distinguisher can also be built against $F(x)=E(x)\oplus x$.

Right now I fail to find a distinguisher for $F(x)=E(E(x)\oplus x)$, but that's not even a weak security argument. Update: If the security of that is unprovable, I'm still interested by a distinguishing attack, in order to get a feeling of how insecure in practice that could be.
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.