As said by others earlier, resizing/up scaling images kill the quality.
And for hd wallpapers check out :
www.wallbase.net Its the best out there IMO.
EDIT:
@OP: That liquid resize does seem to work with minimum quality loss. You can try it out, its really easy. I used it's GIMP plug-in but the results were not that satisfactory.