The universe about halfway through recombination (it was a long process but at the halfway point, it's flips to being mostly clear), much like the universe today, has a temperature. Today the temperature of the universe is about 2.7K, but at recombination it was around 4000K. This temperature corresponds to the blackbody radiation profile of the universe. Thanks to inflation, this radiation profile is almost perfectly isotropic and almost perfectly fitting to a perfect blackbody curve (He said, perfectly overusing forms of the word "perfect" in this perfect sentence).
At the time of recombination, the universe turned from an opaque mess to clear space. But what did it look like? Today, empty space looks black. If you stare out to the farthest reaches of emptiness, you'll see nothing. The nearly isotropic background radiation produces a temperature profile for a 2.7K curve. Most of the energy of that curve is way outside the range of the visible spectrum, which is why empty space appears black. At recombination, our isotropic radiation profile corresponds to 4000 K and looks something like
I made this plot using Mathematica and you can see that the visible spectrum resides in a significant portion of the emitted radiation. So that means if you were to stare out into the abyss of empty space at the time of recombination, empty space would look like one solid, non-black colour (it's actually an orange colour). It would also be excruciatingly intense. Imagine if everywhere you looked was like looking at the surface of a star (On the bright side, you wouldn't have to worry about vampires any more).
As time goes on and the universe keeps expanding, this background colour will (relatively) soon fade (red-shift) to the black we know so well today.
If you want to see the specific colour that we would perceive at recombination or at any other temperature, go to Wolfram|Alpha and type in "Wien displacement law for [T] K" except replace the [T] with a desired temperature (4000 for our case).
Think that's cool? Then think about this: the original colour of empty space (and if you're an originalist, the true colour) is not black, it's orange. Before this, empty space was hotter, but it was opaque so we can't really talk about the colour of empty space then. And before nucleosynthesis is too short of an amount of time to count. So space is originally orange, it just shifted to black because it expanded. Mind=blown
What the hay, here's the colour we'd perceive empty space looking like: