You cannot avoid losing quality when reducing the size of an image; one can hope only to mitigate the quality loss.
When resizing images in Photoshop, the default is to use a softer Bicubic sampler; the comment above to use the Bicubic Sharper would be a good start. It is not, however, always appropriate for all images.
Second, I suggest sticking to multiples of the image width and height. For example, if your original image is 1000x1000, you should get very acceptable results at 250x250, 500x500, 750x750. 398x398, however, is apt to look a bit more blurry.
Hope that helps.