I only have a few materials at my disposal, but here are my impressions:
Teach Yourself Chinese
There is a lot of material in here, however the dialogues are poorly organized and the CD recordings (at least in the early chapters) are so slow that they will do little to prepare you for the spoken language in the real world. However, unlike some books there is a good amount of grammar, accurate pinyin as well as hanzi transcriptions for much of the text. For learners it wouldn't be my first choice, but there are worse places to start out.
Pimsleur Complete-- Mandarin
Not exactly a textbook, but since I've done it I'll give my thoughts. Too expensive for what it does, and if you're new to Chinese you'll have to do the first few lessons 3 or 4 times before the tones and sounds sink in to where you can remember anything. The course is pretty boring, however by the end of it the tones will make sense and you'll be saying some basic correctly vocabulary without effort. Worth a look if your local library has it.
FSI Chinese
Available
for free online, I've barely scratched the surface thus far, but it appears to be a richly detailed, extremely thorough guide to learning Mandarin. Since it is also very technical, I wouldn't recommend it for the casual learner. Still, after I finish a few of my other language-oriented goals, I do look forward to tackling this one formally.
The Lady in the Painting
If you already have some familiarity with the language, this is quite a find. The included CD is almost more valuable than the book, seeing as it contains not only audio recordings for the entire story, but also the entire text in both traditional and simplified characters. If you already know a few hundred hanzi, this one definitely worth your time and money.
Michel Thomas-- Mandarin
I've done the 1 hour demo. Friendly instruction at a relaxed pace, but the amount of expressions/vocabulary you'll learn over 8 hours is quite limited. I'd recommend it if you find yourself truly stuck in getting started.
iCED Free and
DianHua for the iPhone/iPod touch
Not textbooks either, but these free dictionaries are simply awesome. If you've got an iPhone or iPod touch, there's no excuse not to have them!