I think a very important factor in all of this remains the source itself. The source, not being your iPod, but the digital files which are stored on the iPod.
You have some great suggestions for maximizing the quality of what is there, but a CD player runs a high quality, industry standard source (CDs) through your system. They may vary in quality significantly, but you tend to get good to excellent quality from them.
Digital files, in comparison, can run from high resolution audio with phenomenal quality, to far worse than cellular telephone quality. You can't easily tell the difference from one to the next, and even file size differences don't guarantee that a good encoder was used in the process. So, with 13,000+ songs, and a request for the most quality, that is the starting point. The fact that there are many different levels across the songs indicates to me that a single, high quality, encoder was not used, and that there may be a mix of different encoders, and different quality standards for the source itself.
No, not necessarily the case, or the cause, but certainly something that I recommend you be fully aware of.