Another common example would be a course in number theory. A common topic in number theory is public-key encryption, much more in-depth than is sometimes covered in other courses. In addition, the techniques that you learn in such a course can easily be applied to any "number-crunching" you would need to do. Here is an example:
Problem 1 from Project Euler (http://projecteuler.net/problem=1): Find the sum of all the multiples of 3 or 5 below 1000. A brute-force program for this is simple, but it is much faster if we first notice some patterns: (3 + 6 + 9 + ... + 999) = 3 * (1 + 2 + ... + 333). But then (1 + 2 + ... + 333) = 334333/2 (this would be easily recognized by someone who has taken a number theory class), and so the sum of all of the multiples of 3 below 1000 is 3 333 * 334 / 2. Similarly, for 5, there are 199 multiples, so the sum of all of these is 5 * 199 * 200 / 2. But then we must subtract the multiples of 15, since we double counted them: there are floor(1000/15) = 66, with sum 15 * 66 * 67 / 2. So the answer is (3 * 333 * 334 + 5 * 199 * 200 + 15 * 66 * 67)/2 = 299498.
That was a particularly trivial example - number theory will give you a lot more than some parlor tricks like the above. But this example took a loop through n numbers and reduced it to a single line of simple arithmetic. And for someone who understands number theory, this algorithm is as quick to think of as it is for a typical CS student to think of the brute-force algorithm.
I would also venture that a course or two in "Abstract Algebra" would be both beneficial and accessible to CS majors. This is less immediately practical than linear algebra in the above example, but closer in its style of thought to programming than, say, calculus, topology, or differential equations. The abstraction (which many math majors complain about) would be fairly straight forward for a CS major, I would think.