Selective stretching. Can help. Ie, stretching only parts of the image that aren't going to be noticed. Like empty space, or sky.
Redrawing. You might have to redraw bits at the top and bottom of the image , to make it a rectangle rather than a square.
Crop the sides of the image.
With the ps1, the best way is to look for the same image, already converted. For instance sega Saturn boxes. A lot of the time the same artwork was used, but the Saturn box is already closer to DVD size.