There is no real way around that issue in photoshop. You're resizing the image to the point where the defined pixels are becoming visible. Try finding the original image in a larger size?
The easiest thing you could do would be use Adobe Illustrator, I assume you have it due to having Photoshop already. Drag your image onto a new document, select your image on the document and then live trace it. You can go into tracing options within the function and mess with feathering, blur, fitting, etc.