You can use my suggestion if it is possible to simply apply a color filter to the texture of the unit. If this is not easy to do, then I agree with the author, making a large number of games more fun at the cost of making a small percentage of games less fun seems like a good solution. Especially if the percentage difference is huge.
Of the card ideas, I especially like Colossus. It is very unlikely that 2 different versions of it will be played in the same game. And only the stats need to be changed; the abilities, it seems to me, are good. Nature pvp decks have always lacked a unit like this in the late game.