Would providing shade for my air conditioner's condensor improve its efficiency?
It helps for sure.  There have been a ton of studies done on this and I have read at least 10-11.  At one point in time I was going into a partnership for a "greening" business.  

Your variance is somewhere between 1-15%.  There are a ton of variables.  

Here is an OK study I read a few weeks ago from FSEC.  I personally don't like this study because they are first in a climate that doesn't cool well at night and then they used young trees...  

Variables


The shading of the air coming into condensor is super helpful.  But if you have a 9 foot tree over the condenser in an open field then there is a very small volume of shaded air.  Once your condenser sucks in the shaded air then it gets the hot stuff and returns diminish.  So the first variable is shade volume.  With huge oak trees being optimal and anything less than that losing value all the way down to a bush.
Air temperature in shaded area.  This depends on what is under your tree (grass, rocks, dirt, water...), it depends on how many hours a day you get the shade, air flow, how close you are to house...
Air flow is huge.  The more wind you can push to the unit the more efficient it will be.  One of the things that people do that inhibits this is bushes right next to unit.  Obviously decreases air flow.


So the bigger tree you put there the better but you also want to configure the trees so that the unit gets good air flow.  The price of a tree and your work will be returned for sure and could potentially have a major change on your bills - I could see $300-600 a year in warmer climates.  Also I think a small fence would have no to little impact (restricting air flow).