it doesn't necessarily have to be smaller in width, it just has to have an area that can tile.
i would recommend that the parts of the image that are not tiling don't add up to a width wider than 768 so you keep your 800x600 viewers happy. (not sure i did that on this site)
as for the border, add these to your CSS body attribute:
HTML Code:
body{
margin: 0px 0px 0px 0px;
padding: 0px 0px 0px 0px ;
}
that will take care of the padding.