Starting with PyQGIS documentation - Developing Python Plugins:
icon - a file name or a relative path (relative to the base folder of the plugin’s compressed package) of a web friendly image (PNG, JPEG)
Sure icon is not the most important thing user cares about when needs to use your plugin to do some GIS processing etc. But it should look reasonably meaningful, and ideally nice, right? Any chance to use SVG? If not, and PNG/JPEG icon must be used as above - what should be the dimensions / color depth, any other recommendations?