This is an issue with Photoshop, and has been for a number of years. My background with this was in making vehicle wraps for a company, for their fleet of trucks.. 12 to 20 feet in length and eight feet high.. the truck body.

  Universally, no matter what resample I used, if I had to resize an image for them, it would become "fuzzy" on the edges.. pixellation, really. My standard method of resizing was as you did.. to import into Illustrator and resize, then export. Simple explanation for this.. Photoshop and Illustrator do, indeed handle images differently Raster Vs Raytrace.

"..... and that was when things got interestiing."