I don't think this can really be avoided without using photoshop like you said, to cut off some corners, since its a widescreen monitor your using, the Stretch command will stretch the image to that resoloution, and since they aren't widescreen pictures, your bound to get that.
Centre works because its simply placing an unedited image in the centre of the desktop, so you wouldn't get the problem there.
Can't your monitor go lower for desktop?
1152x864 would fix your problem, if your monitor looked alright in that resoloution.
So I'd try setting it to that
Though saying that, what video card do you have, by what make, Nvidia or ATI?