Native Instruments' now-defunct Vokator plug-in is without a doubt, the coolest, most flexible vocoder I have ever used. It sounds absolutely fantastic and offers seemingly unlimited ways of mangling sound far beyond your bog standard Cylon voice. This flexibility comes at a price, however, and the complexity of the instrument means it is not the most user-friendly plug-in you're ever likely to work with. Even with the manual, it can be a daunting program to master. What clarified everything for me was this extremely thorough set of video tutorials by Mats Claesson.
UPDATE: Sorry for the previously broken link. It's fixed now!