Is there any reason why
replaygain (mp3gain, vorbisgain, &c.) shouldn't be used for this? It's pretty well established in other parts of the digital music community, deals with many of the issues involved (e.g., heavy compression), is being worked on by the empeg crew for the karma? The website is a little out of date, but the background and rational are there. The biggest problem is the complete clusterf--- of mp3 tagging standards.
Once the issue of how to best tag an mp3 file is figured out (last
word was that it worked for newer lame encoded files) it should be rather simple to write a userland program that amalyzes and tags the tune file that could be accessed via a hijack menu. It would of course take a while to analyze and tag thousands of files, but can easily be done on the pc side before syncing files to the player.
--Nathan