Yes, the 256 color will be a different file size.

16x16 w/16 color is 776 in .ico format. Not sure what correct .ico size is for 256, however it is not that important. As long as they work correctly on the various Win32 platforms.