I assume you have $n\to\infty$. If $\epsilon<\frac12$ and $s\to\infty$ then $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k}$$ is very close to a geometric progression at the big end. Together with Stirling's approximation (ignoring the floor), this gives $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k} \approx \frac{1-\epsilon}{1-2\epsilon}\binom{s}{\lfloor \epsilon s\rfloor} \approx \frac{1}{\sqrt{2\pi s}}\frac{1-\epsilon}{1-2\epsilon} (\epsilon(1-\epsilon))^{-s-1/2}. $$ Now you can look for the minimum wrt $s$ by differentiating. I don't get a closed form but it seems that the minimum is around $s=\log_2(n)+O(1)$.

I assume you have $n\to\infty$. If $\epsilon<\frac12$ and $s\to\infty$ then $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k}$$ is very close to a geometric progression at the big end. Together with Stirling's approximation (ignoring the floor), this gives $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k} \approx \frac{1-\epsilon}{1-2\epsilon}\binom{s}{\lfloor \epsilon s\rfloor} \approx \frac{1}{\sqrt{2\pi s}}\frac{1-\epsilon}{1-2\epsilon} (\epsilon(1-\epsilon))^{-s-1/2}. $$ Now you can look for the minimum wrt $s$ by differentiating. I don't get a closed form but it seems that the minimum is around $s=\log_2(n)+O(1)$.

ADDED: Note that the function is not continuous. Due to the floor function, it jumps up by a ratio close to $(1-\epsilon)/\epsilon$ as $\epsilon s$ passes an integer. So there are very many local minima. However, the global minimum ought to be close to the minimum of the function without the floor.