Best way would be to re-scan at a higher resolution. But if that option isn't open to you, then try Genuine Fractels, which is said by many to give really good results.
If you are re-sizing using
PS or any other photo editor, then as you've already mentioned, step resizing usually gives better results.