It is very easy to remove all of the ablum art from an iPod. I know there are programs to do it, and there are some tricks to get it done on Windows (I have a Mac), and some people claim there are preferences (didn't work for me) -- but here is the way I got it done.
I wanted to remove all album art from my iPod because trying to load the Main Menu takes, oh, maybe 1.5 seconds, which is an extremely annoying wait, while the iPod spins up the disk and reads a picture into memory. I don't want to wait that long. I like the little picture that shows with the main menu, but not enough to wait for it. If it ain't instant, it ain't good enough.
I first tried to delete all the album art from my MP3s by selecting all my songs, doing a Get Info, and deleting the album art there. That eliminated the album art in iTunes, but when I sync'd my iPod, the album art was not deleted.
I could have searched for a special program, but I decided to do it the old fashioned way. I opened up Terminal and did rm -r /Volumes/Nameofmyipod/Album Art. Blam-o, the iPod can't display artwork if it isn't on the iPod. I had a minor worry that it would cause problems, but there have been no problems. The solution worked perfectly.