From what I have read on this forum and others over the past two years sums up to this:
Shackles will increase flex, and raise the rear. There is no increase in spring rate, and with the added flex comes earlier sag. Not the best idea if you are towing as you say, but cheaper and easier in the short term.
AAL's will firm the ride a little, and raise the rear. Most AAL's have you take out the helper spring in the origional pack. Because of this, they tent to ride nicer on the big bumps as they don't ramp up as much. A better answer for towing, and will last longer.
A little more info:
-If you use shackles and consequently sag out the rear, I understand you cannot correct the problem by adding the AAL after the fact. Given this, and a little bigger budget, I would go for the AALs if towing.
-As for shocks, a set of Bilstiens will help lessen the tendency to bottom out. The stiffer (10-20%) they are, the more this will happen. Your ride will be stiffer as well.
-Many factory shocks will wear out in the 30-60k mile range. If you feel that this may be part of the problem, simply upgrading to Bilstiens will help. They are tested and I think guaranteed to have 90% of their origional damping at the 100k mile mark.
-It is likely, that a 10% stiffer set of Bilsteins in the rear, with an AAL will be the best full package.
Final disclaimer. I do not own, have no actual experience with, nor have tested the above personnaly. It is only the overall impressions I have made in researching the same issue for myself. Hope this helps more than hinders...
_________________________
"I see" said the blind man to his deaf dog.