The F-16's maneuver envelope is better under 15K feet, but they go much higher. Why do they put in that compromise position?
For most aircraft, the advantage of flying high is that the air is thinner, so you go faster for the same fuel burn.
For fighters, height gives you the ability to dive to gain speed, giving them the option for intercept a lower plane, or run away faster than a lower plane can follow. If they're relying on their own radar, it also allows them to see further around the curve of the earth. As Ron mentions, it also puts you out of range of some SAMs, and gives you more time to react to others.
Lastly, while the F-16's manoeuvre envelope may be better at lower altitude, what matters is the manoeuvre envelope of the aircraft they might have to fight, and the altitude they choose to fight at. The relative difference between the two types is more important than any absolute value.