Tweaking the mp3 files themselves sounds like a definite option, but I don't like the idea of the clipping and thus quality loss that might occur.

I would think that the gain should really be adjusted at the final amplification stage of the empeg itself.
Each file could be tagged with a +ve or -ve adjustment in whatever the granularity output stage allows. This way you could subjectively adjust each file until you get your whole collection just how you want it.
Additionally any of the suggested algorithms for finding the optimum gain could be run over the collection and used as a starting point.

This way you should only have a problem if your adjustment factor for a track pushes the total gain off the top or bottom of the scale.