I would imagine you should select the major on what interests you more; the theoretical side and algorithms or the embedded software / hardware side of things. I'm a software engineer and work with Masters/Doctors from both Computer Science and Computer Engineering. I myself didn't graduate, since we started a company and that took all of my efforts at the time. (And after having a few years of applicable experience the employers don't seem to care too much about other credentials.)
I think the distinction between the two is somewhat blurred and overlap. I've worked on things that needed deep theoretical understanding of the mathematics and algorithms dealing with data, and I've written firmware/device drivers "close to the metal" while helping make design decisions with the hardware designers.) I'm not sure which was more enjoyable as I did enjoy the challenges in each.
As for the job market - accurately predicting the future is very very difficult. You should do your own research in whatever area you think you might live in a few years time if you want to base your decision on that.