Your idea for an algorithm which analyzes the song based on average volume level sounds like a good start, and such a program could be a great starting point for filling out the relative volume field in the ID3v2 tags. Although I think such an algorithm would be a bit more complex than what you describe.

Why do you say this? Is it because you don't think that the average power gives a good measure of the subjective "volume level"? I mean, decibel figures are nothing but relative power differences, there's nothing subjective about those; so the formula I describe is quite precise in that respect.

However, you might be correct in saying that one +20dB song can sound louder or softer than another +20dB song. I'm not an audio engineer, just an engineer.

If you're working on just the source files, the only solution is compression, which is tricky to get right.

No argument here...