This answer will come in two parts, first we will transform the problem into a form that is ammenable to the methods of section 2 of Stanley's paper, then we will show that the above summation is equivalent to that answer.
If we renumber the elements of the permutation so that $1,3,5,\dots$ become $1,2,3,\dots$, and $2,4,6,\dots$ become $\lceil \frac{n}{2} \rceil + 1,\lceil \frac{n}{2} \rceil + 2,\lceil \frac{n}{2} \rceil + 3,\ldots$, then the definiton of $\sim_2$ becomes -- two permutations are equivalent if they can be obtained from each other by interchanging adjacent terms that differ by one except we cannot interchange $\lceil \frac{n}{2} \rceil$ and $\lceil \frac{n}{2} \rceil + 1$.
Parallelling the paper we can define a permutation $\omega=a_1a_2\cdots a_n\in \mathfrak{S}_n$ to be salient if we never have $a_i=a_{i+1}+1$ $(1\le i \le n-1$ unless $a_{i+1}=\lceil\frac{n}{2}\rceil$ and we never have $a_i=a_{i+1}+2=a_{i+2}+1$ $(i\le i \le n-2)$ unless $a_{i+1}$ or $a_{i+2}$ equals $\lceil\frac{n}{2}\rceil$.
Each equivalence class of permutations contains exactly one salient permutation. The proof of this exactly parallels the proof of Lemma 2.1 in Stanley's paper. The lexicographically smallest permutation in each equivalence class is salient, and each salient permutation is lexicographically smallest in its equivalence class.
The arguments of Theorem 2.2 hold as well, the only difference is that none of the factors can cross the $\lceil\frac{n}{2}\rceil$ -- $\lceil\frac{n}{2}\rceil+1$ boundary, and we find that
$$f_2(n)=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^j(n-j)!\ p(n,j)$$
where $p(n,j)$ is the number of ways of placing $j$ non overlapping $2\times 1$ dominos and $n-2j$ $1\times 1$ squares on a strip of length $n$ so that no domino covers both $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$.
Since we know that there are $\binom{n-k}{k}$ ways of placing $k$ dominos on a strip of length $n$, we can place the dominos in the left and right halves independently giving
$$f_2(n)=\sum_{i=0}^{\lfloor\frac{n+1}{4}\rfloor}{(-1)}^i\binom{\lceil\frac{n}{2}\rceil-i}{i}
\sum_{k=0}^{\lfloor\frac{n}{4}\rfloor}{(-1)}^k(n-i-k)!\binom{\lfloor\frac{n}{2}\rfloor-k}{k}$$
Slight modification of the above argument gives a plausible way of computing the number of equivalence classes for $\sim_k$ for small $k$.
Now to show that
$$f_2(n)=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^j(n-j)!
\sum_{\ell=0}^{\lfloor \frac{j}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$
we show that
$$p(n,j)=\sum_{\ell=0}^{\lfloor \frac{j}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$
Simple counting shows that the formula holds for $j$ equals zero and one.
Now we show that
$$p(n,j) = \binom{n-j-1}{j} + p(n-4,j-2)$$
for $j\ge 2$ which will give us the desired result by induction.
There are $\binom{n-j-1}{j}$ ways of placing $j$ dominos on a strip of length $n$ so that at least one of $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ is not covered by a domino. We can place $j$ non overlapping dominos on a strip of length $n-1$ in $\binom{n-j-1}{j}$ ways, and for each of these if a domino covers both $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ we insert a single tile at $\lceil\frac{n}{2}\rceil$, otherwise we insert a tile at $\lceil\frac{n}{2}\rceil + 1$.
Conversely, if we have a placement of dominos on a strip of length $n$ such that $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ are not both covered by dominos. If $\lceil\frac{n}{2}\rceil+1$ is not covered by a domino we shift everything greater than $\lceil\frac{n}{2}\rceil+1$ left one place. Otherwise $\lceil\frac{n}{2}\rceil$ is not covered by a domino and we shift everything greater than $\lceil\frac{n}{2}\rceil$ left one place.
Now there are $p(n-4,j-2)$ ways of placing $j$ non overlapping dominos on a strip of length $n$ such that $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ are each covered by a domino. This gives us the recurrence
$$p(n,j) = \binom{n-j-1}{j}+p(n-4,j-2)$$
for $j\ge2$ which combined with the base cases shows that
$$p(n,j)=\sum_{\ell=0}^{\lfloor \frac{k}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$
I'd prefer to avoid the induction and give a direct argument, but cannot figure out how.
Addendum:
The generalization of the argument in the first half to count equivalence classes of $\sim_k$ gives us
$$f_k(n) = \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^n(n-j)!\sum_{\substack{a_1+a_2+\cdots+a_k=j\\0\le a_i\le\lfloor\frac{n+i-1}{2k}\rfloor\text{ for all $1\le i\le k$}}} \prod_{i=1}^k\binom{\lfloor\frac{n+i-1}{k}\rfloor-a_i}{a_i}.$$
This is much less elegant than the final result for $n=2$, but it is amenable to dynamic programming and can efficiently compute $f_k(n)$ easily for any plausible values of $n$ and $k$.
