I'm not sure what options Paint Shop Pro has, but look for a setting called "Bicubic Sharper" or the like in the resizing dialog. Also run a sharpening routine after resizing.