As Christie said packaging is a HUGE part of the entire process of delivery of prints. While 16x20's are very easy to do with boxes and such from many online stores such as
www.dnlphoto.com larger sizes can be harder since boxes are not made for them.
There are very nice photo bags which you can get your logo on them for larger prints, we use them and they work well (up to 30x40" prints)
We also have very nice DVD packages for negatives and wallet boxes with our logo on them and a whole bunch of other items. We spend lots of money for these items but again it is something that makes you look like a professional over a person with a digital camera.
As far as labs there are a TON of them out there, find one which you like product, but then Customer Service is top notch since they all make mistakes, it is correcting them where it really counts. We use Miller's and Collages.net which after researching them all very in depth I found to be the best lab out there for our business.