Deep space you wont notice much of a difference but colored makes the sky like purple and green and stuff instead of black. I prefer colored off but deep space on.

No, they are not mutually exclusive. However, you can get any of the skyboxes to appear by just by selecting and deselecting the use deep space skybox box. If you turn them both off, you won't have any skybox, just boring old stars.

coloured space boxes turn the "sky" different colours, like soasertsus said. its sorta like throwing a bucket of paint at the wall and seeing what happens

the deep space boxes adds more subtle touches, like more stars, some semi-transparent nebulas like clouds and highlights etc.

if you click each on and off you can cycle through the different styles

having them on at the same does nothign really, the colour overrides the deep one almost entirely, but i play with colour off usually because some of them are just too bright and its hard to see...