The origin of the phrase "nearly free" in the nearly free electron model comes from the fact that we introduce a small periodic potential in a metal lattice as a perturbation to free electrons, so that they are not quite "free". Likewise, what is the origin of the word "tight" in the tight binding model? Why is it called "tight"?
[Physics] Tight binding model
solid-state-physicstight-binding
Related Solutions
Starting with some background information from Wikipedia, we have that under time reversal the position is unchanged while the momentum changes sign.
In quantum mechanics we can express the action of time reversal on these operators as $\Theta\,\mathbf{x}\,\Theta^\dagger = \mathbf{x}$ and $\Theta\,\mathbf{p}\,\Theta^\dagger = -\mathbf{p}$. It is worth mentioning here that the time reversal operator, $\Theta$, is anti-unitary, which allows it to be expressed as $\Theta = UK$ where $U$ is unitary and $K$ is the complex conjugation operator.
As for the creation/annihilation operators used in second quantization the sign changes under $\Theta$ would suggest a transformation of $a_r \rightarrow a_r$ and $a_k \rightarrow a_{-k}$. If you are worried about the fact that $k$ represents a crystal momentum and not a true momentum you can just take the position transformation, which is perhaps more trustworthy, and use $a_k = \sum_r \, a_r \,\mathrm{exp}[ -\mathrm{i} k\cdot r]$ to verify $a_k \rightarrow a_{-k}$ directly.
Using these transformations you should be able to verify that the tight-binding Hamiltonian is invariant under time reversal in position and momentum space for a lattice with or without a basis. Keep in mind that you would generally take the complex conjugate of the coefficients in $H$, however in your case $t$ and $\epsilon_k$ are both real. Its important to remember though, mostly to make sure $H$ stays hermitian.
As far as your comment about $\sigma_y$, this is only necessary if you include spin. Spin changes sign under time reversal so $\Theta\,\mathbf{S}\,\Theta^\dagger = -\mathbf{S}$. In this case, we can formally write $\Theta = \mathrm{exp}[-i \pi J_y]\,K$, which is probably the relation you are alluding to.
According to J.J. Sakurai's Modern Quantum Mechanics one possible convention for the time-reversed angular momentum states is $\Theta | j,m\rangle = (-1)^m |j,-m\rangle$. This suggests that with spin indices the creation/annihilation operators transform like $a_{r,m} \rightarrow (-1)^m\,a_{r,-m}$ and $a_{k,m} \rightarrow (-1)^m \, a_{-k,-m}$ under time reversal. From what I understand, most spin Hamiltonians will be invariant under this transformation. An example when this is not the case would be in the presence of an external magnetic field which couples to the spins through a $\mathbf{S}\cdot \mathrm{B}-$like term.
It is interesting how even in the absence of an external field the groundstate of spin Hamiltonians can still sponanteously break the time reversal symmetry present in $H$, but rather than discuss this myself I will direct you to this very well written answer.
The relationship of free electron to tight binding is understood via the Kronig-Penney model. In the Kronig-Penney model a series of quantum wells (particle-in-a-box) are separated by somewhat low walls which allow tunneling between the wells. In the free electron model we start by ignoring the walls and just "folding back" the parabolic energy vs. wave vector relationship and then using the potential of the walls as a perturbation. In the tight binding model we look at solutions to the states in the individual quantum wells and then see how they are modified by interacting with their neighbors. So, from a free electron view point, the lowest state has $k=0$ and would model an $s$ orital. The next state up is just a single wave cycle, so it looks like a $p$ orbital, etc... Within either model you never exhaust the possibilities, you just go higher and higher in energy with more nodes. When the height of the walls is low relative to the energy, the states look like free electrons and when the walls are high they look like the solutions of stand-alone quantum wells (and the band structure is relatively "flat"). For intermediate cases the solutions seamlessly transition betweeen the two models.
Best Answer
In essence, you are kind of on the right path. Going to Ashcroft & Mermin's Solid State Physics text (from the 2d edition):
So, the crystal Hamiltonian is treated as the atomic Hamiltonian plus some correction term that accounts for the periodicity of the lattice.
Consider it as the opposite of the 'nearly free' case - you assume that everything is tied closely to the lattice atom, except for a small correction that lets some electrons be free enough to make the crystal.