While the average damage doesn't change much, the distribution of damage changes quite a bit. For the sake of this discussion, I am only going to address situations where it goes from rolling one dice twice to roll one + max, since the OP doesn't discuss how things like sneak attack would be handled.
The average damage for rolling 2 n sided dice is n + 1, whereas the average damage for rolling one die and taking max on the other is (3n+1)/2. That means the difference in average damage is (n-1)/2, which scales linearly with the number of sides on the die. That is a reasonable way for the damage to scale with the number of sides on the dice and a reasonable "bump" to damage.
However a lot of what playing a system feels like doesn't have to do with average rolls, it has to do with the distribution of rolls and real difference between the two methods is in the distribution of damage dealt. The sum of rolling two dice approximately follows a triangular distribution, whereas rolling one dice and taking the max of the other is uniform. Below is a graph showing what the probability of rolling each possible value is for a d12 to illustrate what that looks like in practice.
As you can see, the probability of getting average damage for rolling two dice actually doesn't change when you switch to roll one + max; it is still 1/n. The real difference is that the odds of getting higher values of damage go way up, with with the higher the value is, the more the odds of getting that much damage increase. The odds of rolling max damage go from (1/n)^2 to 1/n. That means the increased probability of rolling max damage is multiplicative with the number of sides on the dice, meaning the effect is much bigger for a high valued dice like a d12 than for a small valued one like a d4.
From a practical standpoint, this means that not only will your average damage go up, but the game will feel much "swingier". When rolling two dice, most of the time you will roll close to average damage (as seen with the triangular shape of the probabilities), but with rolling one and maxing the other, you will roll somewhere between the average of roll 2x and max damage with equal probability. This means max damage will happen much more often. It also means you are doing more favors for your fighter with a greataxe than for knife wielding assassin.
As Dale M points out your PCs are going to feel this more than your NPCs because they get hit more often. Once again, on average, this may not be a huge difference in the amount of damage they take in a day. However, since you are greatly increasing the odds of those high valued crits, that also means that your odds of a PC getting absolutely trounced goes up drastically as well. PCs usually don't die on days when things do average damage, they die when the bad guys happen to roll well.
Since you are drastically increasing the odds of bad guys rolling well and that only needs to happen one session to kill a PC, you are also increasing the odds of PC death.