You've created an MFC app. Taking a dialog-based app as an example, look at the source for your main window(dialog) and check out the constructor. You'll see this:
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
But LoadIcon can only load icons which are SM_CXICON x SM_CYICON pixels big, which is nearly always the 32x32 version. When it needs a 16x16 version, such as for your titlebar, it squishes that up. Yuck. Instead, replace the code above with this :
m_hIcon = (HICON) LoadImage (AfxGetInstanceHandle(), MAKEINTRESOURCE(IDR_MAINFRAME), IMAGE_ICON, 16, 16, LR_DEFAULTCOLOR);
and lo, there shall be rejoicing in the land...