Lots of people's complaint back then was the model and name - There was little, if anything, about the weapon upgrade mechanic. (Which always had the potential of getting tweaked) In fact, I pretty much remember you having a say about this on the ol' BlizzForums; I went to look, but unfortunately they only go back 5000 posts...
Anyway, we're not talking about 'classic' C&C interpretation of veterancy, or even one for all units (Which I'm also against) just an upgrade (for one unit or unit ability) of some type based upon that units kills. the balancing for that wouldn't be that terrible IMO.