If you relax the independence between $\epsilon$ and $\Delta t$ to be "approximate", i.e. use a method which has a really large stable region even if it's not A-stable, then there are plenty of methods which can get good performance. A standard set of methods for this are the Backward Differentiation Formulas (BDF) or the Numerical Differentiation Formulas (NDF). Usually these implementations get quite complicated because the lower order BDF/NDF methods have better stability, so they are normally implemented as variable-timestep and variable-order. For lower tolerance but faster solving one usually uses Rosenbrock methods of orders 2/3 (which is also easier to implement). [Note that although the BDF methods are not A-stable, the stability region always includes the full negative real axis, meaning that for a lone real-valued ODE like the one you have here, these methods are stable for any $\epsilon$ and $\Delta t$. But that fact doesn't generalize to systems of equations or complex-valued ODEs].
So these give implicit methods. However, as you noticed, the implicit methods do not necessarily have a unique solution for what is the next step. How do you choose one? Normally, you assume that your previous timestep is close enough that whatever root finder you use (Newton's method, or others) is going to converge to "the right one" (here you have a positive, a zero, and a negative solution so it's easy to tell when it fails). This has a timestep assumption in there that the derivation of the implicit method doesn't account for, which could lead to some unexpected issues. If this ends up giving you issues, one way to deal with this is to make some kind of a Predictor-Corrector method where you use a Runge-Kutta 4/5 step to produce an estimate for the step (or split the timestep and do a few low-order but stable explicit steps to get an estimate), and use that estimate as the initial guess for Newton's method. This estimate should be closer to the true step, at least enough that Newton's method will now converge to the right place.
Dealing with stiff problems has a lot of research behind it. Not only that, but it has years of software development. So if you're really looking for solvers which make a good compromise between speed and accuracy on hard problems, you should try to stick to tried-and-tested software. You can directly call some of the classics, or you can use wrappers in a higher level language (MATLAB,Python, Julia (wrappers to Hairer and other algorithms coming really soon!)).