MP3 files have no data in them beyond audio data. Folks have come up with schemes to attach metadata to them. The most recent one is called ID3v2. It (usually) comes at the beginning of the file so as to work better when the MP3s are streamed. The pictures you embed in them are placed in that structure at the beginning of the file. The main drawback to putting them at the beginning of the file is that it makes them hard to edit. If it was at the end, you could just chop it off or add more space, but, at the beginning, you have to rewrite the entire file. The folks who developed ID3v2 recognized this problem and decided to work around it by allowing for there to be blank space in the ID3 tags. Blank space is usually added at creation time so that new tags can be added easily. This also means that when you delete a tag, it can just be marked as blank space so that you don't have to rewrite the whole file. This is why your mp3s aren't getting any smaller. Your tagging program might have an option somewhere to compact the tags. Look for that. It may well be under a different name than compact, but it ought to be there.

Unicode is a method by which any known alphabet can be encoded, from English's to those of accented European languages, to Greek and Cyrillic, to the massive alphabets of Oriental languages. The specifc method used in ID3v2 (except the most recent version, which is not widely implemented yet) would result in doubling the space required for English words. If you don't need it, I wouldn't advise using it.