I have implemented the Add16 as recommended in the book, starting with one half adder followed by 15 full adders. With this structure however aren't you left with one pin unused, the carry pin on the last full adder. Is it better practice to create a new gate that doesn't have one pin left unused?
An unused output pin is not a problem. In fact, it is a rather common hardware experience. Parts are made to be as general as possible (within reason) and one simply ignores outputs that are not needed. This is especially common in various type of flip-flops, where the internal construction requires both the true output and the inverted output. Since the inverted output is often useful to hardware designers, it is supplied on an output pin.