In terms of paper, semigloss seems to be a favorite, though I find that if you find a shop willing to print on magazine paper (which I believe is a semigloss), the accuracy is amazingly close.
As for the size of the sheets, A4 (international) or Legal (US) is the size you want to aim for, unless you're going to a print shop, which will allow for more paper size options.