How are his books--I've never read any but hear great things? Is there a solid book to start with?
His books are mostly fantastic, and they're pretty varied. The best entry point is probably
The City & The City--it's his shortest, and of his most focused. He employs an interesting writing style on it that sounds almost like it's translated, so don't let that deter you.
It is, however, of his least 'fantastical' stories. If you want to go for something a bit more out there,
Embassytown's a good start.
Kraken's a really fun mash-up of nerd ideas into a modern day detective story. He also has a trilogy of books set up in an almost D&D/steampunk world starting with
Perdido Street Station that positively overflows with ideas, but clearly demonstrate a younger writer.