I enjoy my Timbuk2 bag, which is one of their DeeDog models, in my 1st racing team colors and an embroidered team emblem (Aurora Cycles, Seattle, WA). It can easily accomodate a medium sized dog. Or a bike helmet and floor pump.
Although many companies now make courier bags, of special note is Ortlieb, a German company. They make a series of bags for messengers. All their products are waterproof. Not just water-resistant, but waterproof to the "the-water-pressure-will-squash-you-like-a-grape-before-this-bag-will-leak" kind of waterproof. | 
