This problem can be solved in polynomial time in the manner alluded to by Yves Daoust in a comment. Specifically, I'll show that there exists an optimal solution in which every input point "above" some line through the origin can be placed in one part, and every other point in the other. This enables a simple algorithm involving $n-1$ steps, in each of which we guess the location of the threshold line to be between the $i$-th and $(i+1)$-th points taken in increasing order of angle from the $x$ axis, form the two parts accordingly, and optimise each part separately using least squares as usual; the solution with the lowest sum of costs is overall optimal. A slight wrinkle is that points on the $y$ axis can be assigned to either part without affecting the outcome, but this only makes it easier to find an optimal solution: We can ignore these points initially, then add them to either part at the end. This also conveniently avoids having to deal with infinite gradients.
What made the optimality of this algorithm challenging to show was actually the amount of "detail" in the objective function of the original problem statement, caused by the (usually desirable) fact that the $\beta_i$ parameters were "hidden" (replaced with their closed-form optimal solutions). I wasn't able to make progress on that original problem statement. Once I focused on the later expression explicitly involving $\beta_i$, the proof was much easier. The key is to treat $\beta_1$ and $\beta_2$ as being given, rather than being implicit quantities inferred from the data. What I in fact show below is that, for any fixed pair of distinct slopes $\beta_1$, $\beta_2$, all optimal solutions partition the input points on either side of the line through the origin with gradient $(\beta_1+\beta_2)/2$, with free choice of part for points lying exactly on this line. Any solution for given $\beta_1$, $\beta_2$ that violates this can be strictly improved by changing the part assignment of the erroneous points without changing $\beta_1$ or $\beta_2$, and this suffices to rule out such solutions from optimality (the fact that $\beta_1$ and $\beta_2$ can be reoptimised after "fixing" the partition to further improve the total cost is actually irrelevant to the proof). In particular, this rules out all "nonconvex" solutions -- that is, solutions in which the assigned partition changes more than once when considering points in increasing angular order.
Proof sketch
Assume w.l.o.g. that $\beta_1 < \beta_2$.
In the expression $$\min \sum_{i\in S}(y_i-\beta_1x_i)^2+\sum_{i\in \bar{S}}(y_i-\beta_2x_i)^2$$ each $(x_i, y_i)$ participates in exactly one of two ways: either as $(y_i-\beta_1x_i)^2$, or as $(y_i-\beta_2x_i)^2$. Choosing the smaller of these independently for each $i\in S$ is sufficient to minimise the entire expression. For simplicity I'll drop the subscripts on $x$ and $y$.
I'll now show that $y/x < (\beta_1+\beta_2)/2$ implies $(y-\beta_1x)^2 < (y-\beta_2x)^2$.
\begin{align}
&y/x < (\beta_1+\beta_2)/2\\
\implies& 2y < (\beta_1+\beta_2)x\\
\implies& y-\beta_1x < \beta_2x-y\tag{1}
\end{align}
The RHS must be positive:
\begin{align}
&y/x < (\beta_1+\beta_2)/2 < (\beta_2+\beta_2)/2 = \beta_2\\
\implies& \beta_2x-y > 0\tag{2}
\end{align}
The LHS could be $< 0$, or $\geq 0$.
Case 1: $y-\beta_1x < 0\qquad(3)$
\begin{align}
\implies& \beta_2x-y > \beta_1x-y > 0\textrm{, with the first > because }x > 0\textrm{ and }\beta_2 > \beta_1\\
\implies& (\beta_2x-y)^2 > (\beta_1x-y)^2\textrm{ since both sides of }\beta_2x-y > \beta_1x-y\textrm{ are positive by }(2), (3)\\
\implies& (y-\beta_2x)^2 > (y-\beta_1x)^2\textrm{ and we are done for this case.}
\end{align}
Case 2: $y-\beta_1x \geq 0\qquad(4)$
\begin{align}
\implies& y-\beta_1x < \beta_2x-y\textrm{ from }(1)\textrm{ with both sides nonnegative by }(2), (4)\\
\implies& (y-\beta_1x)^2 < (\beta_2x-y)^2\\
\implies& (y-\beta_1x)^2 < (y-\beta_2x)^2\textrm{ and we are done for this case.}
\end{align}
In both cases, we establish that $y/x < (\beta_1+\beta_2)/2$ implies $(y-\beta_1x)^2 < (y-\beta_2x)^2$. Similar reasoning shows that this claim also holds with the inequalities reversed. The two results together give a rule to decide which part to assign to each input point.