How theoretical CS majors are is really, really dependent on what college you're at, and what courses you take. To be honest, many CS majors really hate theory, and few colleges will force CS majors to take theory-intensive courseloads. However, you should not interpret this as meaning that there isn't any theory in CS! For instance, looking at the VT faculty list I can immediately tell Prof. Heath (
http://people.cs.vt.edu/~heath/) is a hardcore theory guy. [Trust me on this one.]
If you're interested in a graduate degree, you should be prepared for much more theory. There are certainly non-theoretical CS graduate courses / theses, but they're not as overwhelmingly dominant as at the undergraduate level.
Based on your interests, it certainly sounds like you would be happy as a CS major. I'm not entirely sure what your concern is in the first place, though. (PM me if you need anything specific, or just reply here.)