I have full screen (fills entire screen if 4:3 or has black bars at top and bottom if Widescreen).
I use AVS4You software. (AVS4YOU Best software for you on today's market. Subscribe and download now for free!
, I think) It's the absolutely best software for Audio/Video stuff. You pay one fee and get use of all their software (about 10 programs in all).
Here are the settings I used to create my full screen Videos:
Video: MPEG4 - best quality, 24 fps,320 x 240; Audio: MPEG4 AAC LC 128 kbps, 48000 Hz, Stereo
I still haven't tested all the possible formats that BB can read, but this one gave me good quality and decent file size.