Algorithm: RANSAC would be a good algorithm for this problem, if you think there exists a line such that a large fraction of points lie on that line. (However, if there is no such line, RANSAC is not a good choice.) In each iteration, it randomly selects two points, draws a line through them, and then checks how many other points fall onto that line. It then does many iterations repeatedly, and keeps the best line it has found so far.
Analysis: Suppose there exists a line $L$ such that a fraction $p$ of the points are on the line $L$. Then any particular iteration has a $p^2$ probability of picking two points on the line $L$ and discovering the line $L$. So, if you run RANSAC for $O(1/p^2)$ iterations, then with high probability the line $L$ will be detected. Each iteration takes $O(n)$ time, so the total running time will be $O(n/p^2)$. For some values of $p$, this will be faster than your crude algorithm (which has a $O(n^2)$ running time).
In short, the more points on the optimal line, the faster RANSAC will find it.
This doesn't answer your question about the best worst-case complexity. I don't know if it is possible to beat ${n \choose 2}$ worst-case complexity. I don't know if this is optimal or if there are better algorithms. Also, even in the case where we know there is a line containing many points and where we care about average-case complexity, I don't know if RANSAC is optimal or if one can do better.
