1.
For folios and mats, here are a couple sites to check out:
B&H Photo
Light Impressions
You may also want to try a Google search using "wedding albums" or "professional albums"
2. I'm not sure about the proof question, it may just be a personal preference of the photographer. The image is probably cropped to meet the 4x4 or 5x5 size, then later once the proofs are selected, the entire image is printed. Hopefully someone else will answer that.
3. As for why you lose some of your image when resizing, that depends on what you are doing. If you are trying to resize your image to meet a certain size, say 4x6, the reason you may lose some of your image has to do with the aspect ratio and proportions. These article may help explain it better:
Aspect Ratio and Cropping Cropping