Try exporting from Premiere as DV, and use something else to convert to Xvid
Try the free program
Virtualdub for example. You can select the parameters in the Xvid output, so you can try various qualities, and see what file size/quality balance suits you best. (Try a small file first - saves encoding the whole lot only to discover it's too big a file or too poor quality!).
Virtualdub can take a bit of effort to learn at first, but there are tutorials out there for it, and it is an excellent program for transcoding, once you're into it.
Shouldn't take 20 hours to encode one hour of Xvid on a duo core!
Regading the 16:9 business. Unfortunately not all players see the 16:9 'flag' set in the encoding software.
With an mp4 file, like xvid, you can change the aspect ratio flag with the freebie program
MPEG4 Modifier.