Well, As far as how large you can go really depends on alot of things. Remeber that many times the larger the print the lower the required DPI/PPI for printing. Bill Boards are amazingly low resolution for thier size. We have in our office 20X30 prints shot off a 2 Megapixel Kodak Professional DCS520. Are they perfect, no not really, but for how they are viewed they are fine. So if your native size is 8X12X300DPI then you should be able to go faily large. You also want to check with the lab, some labs will size your image up for larger printing, others really prefer you give them one that is sized correctly (Although in my experience, the labs generally want to upsize the image for you)

As far as what to send them, Yes lots of color and detail as these are the things that are going to suffer the most when upsizing your images.

Hope this helps!!

JT