I started with "Consider Phlebas" after a suggestion here on HN (that I read Iain Banks), and I don't recommend it as the starting book, it was bit of a letdown (though it's an ok book).

I'm now reading "Player of Games" and it's far better, though maybe the introduction to the "Culture" universe was worth reading the first book.

It seems "Use of Weapons" is the best one, I haven't read it yet.