I've read (in order) Consider Phlebas, Player of Games, Use of Weapons, and Excession thus far. Use of Weapons was the toughest one for me to get through so far. I started it and stopped it a few times over several years and just couldn't get past the halfway point. I eventually got over the hump with it and devour the last half of the book over a couple of days (which is fast for me). So for my money, Use of Weapons is a bad starting point.

My favorite by far is Excession but I don't know that I'd start there. I think the payoff of getting a story from the perspective of the Minds is better appreciated after you've heard about them and their capabilities from a distance in the preceding books.

My pick would be to start with Player of Games. That's the one that was a page turner for me nearly from the jump.