I'd suggest PoG as a starting point to explain what the Culture's about, which I think it does better than CP because the main character in that is not of the Culture. YMMV though.
Read this webpage to get an introduction to the Culture. It's great, and it helps you get through some of the "rougher" edges in the earlier books.
I've bought them three myself and will read them in this order.
then: The Player of Games Consider Phlebas Use of Weapons
Use of Weapons is great, but the writing is poorer than the other two.
Heh. Interesting. I'd say exactly the opposite myself. Not that I dislike the other two - PoG is one of my faves of his SF work - but to me UoW is a vastly better work of literature, both in structure and character development. Less full of SFnal goodies than some of his later work, but all the better for that in some ways.