There is no practical way without custom coding to prohibit duplicates here. Can you count on the customer not leaving the same thing selected twice? If the text is prominent enough they should have no excuse...

As for ensuring a selection, I figured I'd let you get the first part done before introducing that. It is definitely something that needs to be taken care of.

For each option name, make another option value called "Select" or whatever. Add each of them to the product as Default and Display Only. This will show distinctly that they still need to do something, and not allow them to add to cart until they do.