Now, here's the question - if you could get a CS degree'd person, that would be preferable. However, if you couldn't, what's the degree you'd take as a substitute? Art? Philosophy? French Literature?

I dunno about that. I've come across a lot of mathematicians who really suck at programming. That step from the abstract to the concrete can be a doosy.

I've also come across a lot of good programmers with a philosophy & psychology background - but that may be a biased finding on my part since I spent a chunk of my early years around AI folk.

Personally I'd pick any engineering or physics degree before maths :-)