How do I change the displayed icon of my MFC app on the fly?

You need to use LoadImage to explicitly load the small version of the new icon, and then use SetIcon to display it:

HICON hAIcon = (HICON) LoadImage (AfxGetInstanceHandle(), 
                                  MAKEINTRESOURCE(IDI_ICON1),
                                  IMAGE_ICON,
                                  16, 16,
                                  LR_DEFAULTCOLOR);
SetIcon (hAIcon, FALSE);

Remember that if you want both the 32x32 and 16x16 icons to change, you'll need to load and set both versions.