If you're just a normal science fiction fan, start with Use of Weapons. It's complex and sci-fi-ish enough, but not as hardcore as Excession. The plot is amazing. To me it is one of the most memorable books of science fiction that I've read. It really made me question some basic beliefs about ... well, you'll see.
If you're a normal person, who wants a slightly softer intro into the Culture universe, or someone who's not particularly into science fiction, Player of Games is a great starting point because it is less about the tech and more about the ideas and the people, but nevertheless a great book.
Ultimately, the only one I wouldn't start with is Consider Phlebas, which is good, but imho nowhere near as good as the rest. To me, Consider Phlebas was about the same level as, say, the Reality Dysfunction by PFH - great space opera, fast paced, gripping, but not exceptional in any way. Every subsequent book (with very few exceptions) is not just great, but also unique and different from all the other science fiction books out there.