The culture ones (with the exception of player of games) are pretty space shippy – although thats not a bad thing. His books tend to focus on the characters, although these may well be AI rather than human.
I would start with Against a Dark Background – its one of the best books I have ever read. Its just got that something that grabs me, something about the depth of the main character and the desperation shes put through, I dont quite have the words for it but it will stick in your memory. After that Surface Detail is superb. Then I would suggest Use of Weapons, then you might as well dive into the full blown culture books, Excession is the best example there.
I dont really like State of the Art, he doesnt seem to do the short stories as well in my mind. I much prefer Zima Blue, a book of short stories by Alasdair Reynolds, and would suggest thats where to go in sci-fi to begin with for your short story fix.
I doubt you will regret reading any Iain M Banks – perhaps the real place to start is whatever your local charity shop has for 50p?