Yeah. That's about right. A lot of my album art is larger than 20kb, but not by much. Most of my artwork comes from Amazon.com, and they're pretty good about optimizing the artwork for good quality at low file sizes.
The point is that every 100 songs will take up an extra 2mb (assuming 20kb per image) so for 1000 you'll lose 20mb, or just a few songs worth of data.
With my 192kbps collection, all with lyrics and artwork (the lyrics take up only 2-3kb per song, which is hardly anything) I only get about 700 songs on my 4Gb nano, which is plenty.