How broken is LCG in the case of partial output?
Yes, there are techniques based on lattice reduction that are faster than brute force.  See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to $O(2^{(n - k)/2})$ if $k \ge n/2$: see https://crypto.stackexchange.com/a/10609/351.