I would recommend reading Excession after you read at least 2 or 3 other Culture books. It has such a focus on the Minds that I don't think it can be fully enjoyed until you have become familiar with The Culture first.
Favorite Culture novels are Player of Games, Use Of Weapons, Consider Phlebas and Excession.
I love both his SF and mainstream though. I like how he often gives breath and life to being Scottish in a way that few others do, and in a way that reminds me of Trainspotting. Scotland often only appears in literature as a place of history and clans, and I enjoy works that capture something of what it is to be a Scot in this modern world. I felt perfectly at home in many of his non-SF works too.
Favorite non-SF are The Wasp Factory, The Crow Road, The Bridge, Walking On Glass, Espedair Street, and Complicity.
The televised adaptation of The Crow Road was very good too. I saw The Wasp Factory as a play and really enjoyed that too, it was an interesting modern production using television sets and things.
By and large it is Banks' characters I like. They always seem very believable to me, full of all the flaws and nobility that I find in most people. Even the 'perfect' Minds are full of their flaws. And perhaps I feel so at home because his politics and world view are ones I can relate to - the concept of The Culture where everyone is free to do as they wish as there is no longer disease, money, and all that, is very appealing! And the Star Trek version of that seems kind of bland and banal in comparison to the vibrant canvas of The Culture where people indulge in all sorts of strange things, just like people would if given that freedom.
So, I actually like both of sides of his works. He does have some novels I don't much care for too, again on both sides. That said, though, he is one of only two authors where I own pretty much ALL their books
PS - been trying to find the movie of Complicity (renamed Retribution over in the US) for some time, but not tracked it down yet. Trying just to rent it rather than purchase it, just in case I don't like it that much! Anyone seen it?