Depends on your printer, but I use Epson's 3-star glossy photo paper for my covers.http://www.epson.com/cgi-bin/Store/ProductMediaSpec.jsp?BV_UseBVCookie=yes&infoType=Overview&oid=-9782&category=Paper+%26+MediaThen again, I have an Epson printer so you may want to go with a different one depending on your manufacturer.
I don't know is Semi-gloss available in Legal size.I'm European ( ) and I use A4 size which is our basic size.
Is it true that UCG's game covers cant fit onto normal sized paper which is why you need legal sized?
If by normal you mean Letter-size, then the paper will be too short unless your printer is capable of printing borderless, which most printers aren't capable of. That's why Legal-size is recommended (or A4, which is "normal" size outside of the States).