tl;dr:

1. Right-click the StarCraft shortcut
2. Click "Properties"
3. Click "Change Icon..." button near the bottom
4. Select the original icon from the list
5. Click "OK" button

If you didn't know, Blizzard released the first patch for StarCraft since 1999. The patch includes various fixes and updates to make the game compatible with modern OSes and Battle.net. It also makes the game 100% free (including Brood War expansion) to get people excited for the upcoming remastered version. Get all the specifics and download the installer from starcraft.com. Run the installer to patch your existing original installation or to do a complete fresh install.

The patch updates the game's EXE icon to a modernized version which I am not a fan of (kills the nostalgia). However, they were nice enough to include the original icon in the EXE as well. Follow the instructions above to get the original icon to display on your shortcuts.

I tried using Resource Hacker to change the first/default icon stored in StarCraft.exe (Right-click Icon folder, replace icon...) but afterwards attempting to launch the game resulted in an immediate crash. I prefer this method over changing shortcut icons. Anyone got any ideas on how to accomplish this?