Personal MP3 players e.g. iPod, smartphones - aim for small/medium size images of around 300x300 pixels. The higher resolution players are around 800 pixels in one dimension, so 300x300 leaves just under half the screen for the artwork.
Tablets e.g. iPad - Aim for medium/large images of 500x500 and larger.
Computer based software e.g. iTunes, Winamp - depending on the size of your player window, aim for medium/large images of 500x500 are larger.
Large TVs - Aim for large images of 900x900 pixels and larger. Again, this depends on the resolution of your TV's software and the screen real estate afforded to your artwork.
I generally use 500x500. That's a good general size, that works well in most places I use images. It's not so large as to overwhelm most players (some of which balk if the image is too large), nor so small as to be a thumbnail on larger viewers.
When I search for images to use, I try to avoid using ones smaller than that, if others can be found. And if the image I like is larger, I use Irfanview to reduce it to 500x500 before I save it in Mp3tag. I don't like Mp3tag's image reduction process, as it's fixed at 70%, which is too much compression. Using 90% is a better alternative. I wish Mp3tag offered different image compression choices.
I just used the new image reduction with configurable compression/quality setting. Works great! I used to spend a fair amount of time pre-editing images before I added them in Mp3tag, this will save time & effort by doing it all in one program.
I like to see cover art when I play music in my vehicle. But it won’t display any art that’s bigger than 235 x 235 pixels. So the size you pick should correlate to whatever player you want to use.