Edit: my answer

I emailed Noga to ask him; here is his response (touched up slightly for MO; any errors in what I post are probably mine rather than Noga's). The only details not present are the required applications of Stirling's formula.

Here is another rough argument for a lower bound, hopefully I'm not making a silly mistake. Also, I would hope there is a slicker argument then this, but here goes.

We're going to construct the permutation iteratively. First, build a random function $f:[n]\to [n]$ as follows.First fix a uniformly random permutation $\sigma$, then, for $i=1,\ldots,n$, select $f(\sigma(i))$ uniformly from among $\{\sigma(i),\ldots,\sigma(i)+n/2-1\}$, independently for each $i$. Say that $i$ is bad if there is $j < i$ such that $f(\sigma(j))=f(\sigma(i))$.

Not hard to check using standard concentration bounds that the proportion of bad guys is very close to $1/e$, except with extremely small probability (don't count bad guys, count the total number of indices $k$ for which $|f^{-1}(k)| \geq 2$).

Similarly, in every interval $[k,k+n/2)$ (mod n), the proportion of empty spaces is very close to $1/e$, except with extremely small probability. (Here you can take "very close" to mean, say, up to a multiplicative error of $O(n^{-1/3})$ except with probability $e^{-Cn^{1/3}}$ for some $C > 0$. I want strong bounds

Edit: my answer was useless so that I can guarantee structure after the procedure is finished, because we are going to iterate.)

Similarly, at each step $i$ of the process for building $f$, in every interval $[k,k+n/2)$ (mod n), the number of good choices for $f(k)$ is very close to $(n/2)e^{-i/n}$.

It follows straightforwardly from the above that when the $i$'th good choice was made, the number of available good choices was very close to $(n/2)(1-i/n)$ for all $i$ (note that there whp be a total of around $n(1-1/e)$ good choices made.

Now suppress the bad values $k$ from the domain of $f$ to obtain a partial permutation. It follows from the above that the number of distinct partial permutations that can arise is very close to \[\prod_{i=1}^{n-n/e} \frac{n-i}{2}.\]By the above concentration bounds, we know that when we finish the above, with high probability there are about $n/e$ values missing from the domain (and from the range) of our partial permutation. Furthermore, these missing values (in both the domain and the range) are uniformly distributed in every interval of the form $[k,k+n/2)$.

Repeat the procedure on the unchosen values of the partial permutation. This will allow you to fill in all but about $n/e^2$ of the remaining unchosen values, while maintaining the required concentration. Keep doing this until there are $u = o(n/\log n)$ unchosen values. The total number of partial permutations that can arise to this point is very close to \[\prod_{i=1}^{n-u} \frac{n-i}{2} = \frac{n!}{u! 2^{n-u}} = \frac{n!}{2^{n(1+o(1)}},\]since $u!=o(2^n)$ for $u$ this small.

It is not completely obvious that we can finish building the permutation at this point, but deleted itwould suffice if, for all $k$ missing from the domain of $f$, we could choose $f(k) \leq n/2$ when $k \leq n/2$ and $f(k) > n/2$ when $k > n/2$. For this, we need that the number of empty spaces in $[1,n/2]$ is the same for the domain as for the range, which might not quite be true.

However, if instead of maintaining that empty spaces in intervals of length $n/2$ are well distributed, we maintain this property for intervals of length $n/4$, then we can fix this problem by first matching some unmatched elements of $[n/4,n/2]$ to elements of $[n/2,3n/4]$, in order to ensure that the number of empty spaces on each side of $n/2$ is the same for the domain as for the range. Having done this, we can complete the permutation while maintaining the required property.

Here is another rough argument for a lower bound, hopefully I'm not making a silly mistake. Also, I would hope there is a slicker argument then this, but here goes.

We're going to construct the permutation iteratively. First, build a random function $f:[n]\to [n]$ as follows. First fix a uniformly random permutation $\sigma$, then, for $i=1,\ldots,n$, select $f(\sigma(i))$ uniformly from among $\{\sigma(i),\ldots,\sigma(i)+n/2-1\}$, independently for each $i$. Say that $i$ is bad if there is $j < i$ such that $f(\sigma(j))=f(\sigma(i))$.

Not hard to check using standard concentration bounds that the proportion of bad guys is very close to $1/e$, except with extremely small probability (don't count bad guys, count the total number of indices $k$ for which $|f^{-1}(k)| \geq 2$).

Similarly, in every interval $[k,k+n/2)$ (mod n), the proportion of empty spaces is very close to $1/e$, except with extremely small probability. (Here you can take "very close" to mean, say, up to a multiplicative error of $O(n^{-1/3})$ except with probability $e^{-Cn^{1/3}}$ for some $C > 0$. I want strong bounds so that I can guarantee structure after the procedure is finished, because we are going to iterate.)

Similarly, at each step $i$ of the process for building $f$, in every interval $[k,k+n/2)$ (mod n), the number of good choices for $f(k)$ is very close to $(n/2)e^{-i/n}$.

It follows straightforwardly from the above that when the $i$'th good choice was made, the number of available good choices was very close to $(n/2)(1-i/n)$ for all $i$ (note that there whp be a total of around $n(1-1/e)$ good choices made.

Now suppress the bad values $k$ from the domain of $f$ to obtain a partial permutation. It follows from the above that the number of distinct partial permutations that can arise is very close to \[ \prod_{i=1}^{n-n/e} \frac{n-i}{2}. \] By the above concentration bounds, we know that when we finish the above, with high probability there are about $n/e$ values missing from the domain (and from the range) of our partial permutation. Furthermore, these missing values (in both the domain and the range) are uniformly distributed in every interval of the form $[k,k+n/2)$.

Repeat the procedure on the unchosen values of the partial permutation. This will allow you to fill in all but about $n/e^2$ of the remaining unchosen values, while maintaining the required concentration. Keep doing this until there are $u = o(n/\log n)$ unchosen values. The total number of partial permutations that can arise to this point is very close to \[ \prod_{i=1}^{n-u} \frac{n-i}{2} = \frac{n!}{u! 2^{n-u}} = \frac{n!}{2^{n(1+o(1)}}, \] since $u!=o(2^n)$ for $u$ this small.

It is not completely obvious that we can finish building the permutation at this point, but it would suffice if, for all $k$ missing from the domain of $f$, we could choose $f(k) \leq n/2$ when $k \leq n/2$ and $f(k) > n/2$ when $k > n/2$. For this, we need that the number of empty spaces in $[1,n/2]$ is the same for the domain as for the range, which might not quite be true.

However, if instead of maintaining that empty spaces in intervals of length $n/2$ are well distributed, we maintain this property for intervals of length $n/4$, then we can fix this problem by first matching some unmatched elements of $[n/4,n/2]$ to elements of $[n/2,3n/4]$, in order to ensure that the number of empty spaces on each side of $n/2$ is the same for the domain as for the range. Having done this, we can complete the permutation while maintaining the required property.