I've never tried this on my own pod cauz i use the Album Art, and i can't guarantee that it won't blow things up, but here's an idea:
If your iPod is set to mount in disk mode, try this...
after updating the pod,
1) open the Terminal application.
2) type this command, but replace <podname> with the name of your iPod:
cd /Volumes/<podname>/iPod_Control/Artwork
3) type "ls" and you will see a few files with a .ithmb extension.
4) type "rm *.ithmb" to remove these thumbnail files.
****be super-careful with the rm command! it could hose your hard disk!
I think that's where the artwork is stored. I have two .ithmb files, and they take up about 100MB.
Again, i've never tried this and have no idea if this will cause problems on the iPod, but it could be a quick&dirty hack to free up some space.
Godspeed!
D.Be