This issue has been quite discussed already (see https://bugs.launchpad.net/notify-osd/+bug/393797).
If the image given to notify-osd is large enough then it will render as sharply as possible. If you are willing to write a resize algorithm that is more efficient than the current gtk ones, then I thank you in advance. Otherwise the only thing to do is to have large covers.
There is nothing particular that the notify-osd / rhythmbox / banshee / exaile / any other player developers can do about that. They should just not resize the cover themselves unless they know the notification daemon will not and unless they explicitely want to control the cover size.