Structural Physical Approximation of Partial Transpose

To make the partial transpose a complete positive and therefore physical map, one has to mix it with enough of the maximally mixed state to offset the negative eigenvalues.

The most negative eigenvalue is obtained when partial transpose is applied on the maximally entangled state which is $$-\frac{1}{2}$$.

Therefore, $$\widetilde{I \otimes \Lambda} = (1-p)(I \otimes \Lambda) \rho + p\frac{I \otimes I}{4}$$ where $$p = \frac{2}{3}$$ will sufficiently offset the values. However, in this paper by Horodecki and Ekert, they say $$p$$ needs to be greater than $$\frac{8}{9}$$, which I can't understand why.

In the paper that you refer to, they are essentially asking "when can we implement the partial transpose map $$\Theta=I_2\otimes\Lambda$$?". So, that means the SPA of this map must be positive. What you have calculated, by comparison, is to ask when the SPA of the transpose map $$\Lambda$$ can be made positive. It might sound like these ought to be the same answer, but adding identity to the transpose map and then extending the Hilbert space is different from extending the Hilbert space and adding identity.
So, you need to be finding the value $$p$$ such that $$(1-p)(I_4\otimes \Theta)\rho+p\frac{I_4\otimes I_4}{16}$$ is positive. As you did, you need to consider the maximally entangled state, but of course it's of larger dimension now. You'll find there's an eigenvalue $$(9p-8)/16$$.