How does increasing the ionic strength of an aqueous solution decrease the activity coefficient?
Thermodynamic activity is essentially the same the chemical potential.  At the solubility limit of a compound, the dissolved species is in equilibrium with the solid species.  For example, a saturated solution of sodium chloride is in equilibrium with solid sodium chloride crystals.  In such equilibria, the chemical potential of the dissolved sodium chloride is equal to the chemical potential of the solid sodium chloride crystals.


  If the ionic strength increases the solubility of an ionic compound, then wouldn't that mean that the concentrations of the ions that make up that ionic compound would increase, and thus the activity coefficient, therefore, must increase to show an increase in activity, otherwise known as the "effective concentration?"


Let's assume that increasing the ionic strength doesn't alter the crystals of solid sodium chloride that dissolved sodium chloride is in equilibrium with.  That means the chemical potential of the crystal is unchanged.  At the solubility limit, the dissolved sodium chloride is still in equilibrium with the crystals, and as before, this equilibrium requires that the crystals have the same chemical potential (aka thermodynamic activity) of the dissolved species.  

If there is more of the dissolved species (a higher concentation), the only way the activity can stay the same is if the activity coefficient goes down. 

So you were right when you wrote:


  ...the activity [is] independent of the ionic strength such that in order to keep the activity the same under higher concentrations, the activity coefficient must be smaller...
  
  This would then bring up the question: is the equilibrium constant, $K$, (determined by the activities of the components in the equilibrium expression) constant even under different ionic strengths, while the "concentration coefficient" (determined merely by the concentrations of the components in equilibrium with one another) does vary under different ionic strengths?


The equilibrium constant is a ratio of thermodynamic activities.  The "concentration coefficient" can vary and will not be constant any time that activity coefficients are not 1.0.  Ionic strength is one of many variables that can affect activity coefficients.  So to conclude:


Yes, the equilibrium constant $K$ is determined by the activities of the components in the equilibrium expression.
The "concentration coefficient" $K_c$ can vary as a function of ionic strength (or other variables).