[RoGuE_STreaK]

There's numerous programs you could use, VirtualDub is free and fairly straight-forward. Get the "unofficial" MPEG2 version (just search for "virtualdub mpeg"), then you can also import mpg.

The quickest way to do the borders is to find the "smart resize" filter, which doesn't come with virtualdub. It adds some more functionality, and makes it easier.
Open your avi, then under "video" go to "filters", and "add..." => smart resize. Say for example your original file is 320x240, keep this setting in the first resize boxes, change the filter mode to "precise bicubic" (better quality), then tick the "letterbox image", and fill this with "320 x 320". Check the preview and scroll forward a little to reset the image, and you will see your new pic!

Actually, you'd probably get best results if you use virtualdub to resize to 128x128, rather than feeding the 320x320 file to the amv converter. But I haven't been doing this, and it seems fine (more experimentation required).

Then mess around with the compression etc to suit your needs.

[EDIT]Actually, faster way, forget smart resize, just use resize, set "new width" to 128, "new height" to 96, choose "precise bicubic", then tick "expand frame" and type in 128 and 128. Done, apart from the recompress.