Smallest real root of a polynomial in a range
I would like to propose mix of Sturm algorithm (to split range into ranges to know how many roots are there) and then run Newton method, which converges very fast with good initial guess.  

Of course for Sturm - only up to first root range found.  

Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all, when degree is equal one).

The main idea behind that is local root finding methods are faster than global ones, but they might diverge to some other place, but you are interested in the first one, so providing good initial guess will put Newton method in the radius of convergence.

The things to add: there might be many roots in small distance, so the main idea was to "pick one" range and start finding it, your idea of finding the slope is very neat, and if you merge the slope finding with initial range picking it seems like boosted Newton for very small cost.
The idea is to also show Newton method which root you are after (otherwise it might go after surrounding one).

About binary search, if you want to apply it until there is one root - yes, indeed, but if the idea is to check more ranges - I would cut it for resources savings.