Finding a minimal width strip which encloses a set of points in the plane
Take the convex hull of your set of points. Then use "rotating calipers" to
find the optimal strip.
What is needed here to make this work is a lemma that characterizes a
potentially optimal solution: Could the optimum occur without one supporting line
through two points ("flush" to the hull)?

Added. Yes, that flush-lemma holds, because more-horizontal strips are preferred. So: for each edge $e$ of the convex hull $H$, 
extend $e$ to a line $L_1$, and let $L_2$ be
the parallel line supporting $H$ on the other side. Compute the vertical distance between $L_1$ and $L_2$.
Select the shortest distance among all alternatives.