If file size isn't an issue then the best thing to do is do a couple of encodes of a movie with DivX/XviD/H.264 and compare to see if you notice anything yourself. If you don't are happy with DivX stick with what you know, if you want to test out H.264 try
Ripbot.
As for the widescreen topic I understand what your on about, some wide screen movies occupy all of the screen but these are not very common.
I'm not an expert though so I'm not sure what the correct terminology is but I do know Pixar calls these "full frame" movies. These full frame movies are not to be confused with full screen movies which are for non-wide TV's & crop the picture.
The black borders are normal for widescreen movies it's just the odd wide movie is done in full frame.
When you encode a movie and it strips away the black border if you try resize so it goes into full frame it will mess up the aspect ratio and make the video look weird on screen, maybe someone else knows any tips in this area as I said I'm no expert.