Sorry for long post in advance.
Please guys, everything is completely calculable and I see here lots of 'I feel this laser to be brighter than another one' in the powers and divergences field. Stop this witch-hunt

So, going to write down some things which you all probably already know (and probably it is floating somewhere in the forum already), but maybe that will help someone.
This divergence vs power thing has wrong approach in most cases. We do not see power, nor the divergence. The parameter which gives visibility of the beam is power density - it's simply power divided by the area of the beam. The area of the beam is mainly determined by the beam waist at the aperture and divergence. Since we usually have divergence in mrad it approx. shows the number of mm added to the waist over the travel distance of 1m, i.e. if we have 1.1x0.5mrad divergence on 4x4mm beam, @ distance 10m we should expect beam to be 15x9mm (4+10*1.1 x 4+0.5*0.5 mm).
Once we clear with that, there are a few cases to consider:
1) Top hat beams. If we have multimode source with more or less uniform intensity over cross section of the beam, we can calculate the power density = Power/(width_x*width_y). Saying that beam becomes 4 times denser if the divergence is 2times lower is too abstract, because in LD case we usually have fast and slow axis with different divergences and usually 'lowering divergence' is understood as correcting FA... which relates to linear power density dependence. If the collimation lens is changed which results in lower divergence it changes both axes, so the power density changes in square dependence.
2) TEM00 beams. If we have singlemode source the intensity cross-section of the beam is Gaussian. In this case it's hard to determine what actually is the 'beam visibility', however it's usual to calculate peak power density. Here how it's done:
We take power density at FWHM as PD=Power/area(FWHM)=Power/(pi*d/2(FWHM)). Since power density is always linear dependent on power, the peak power density is now 2x PD(FWHM). For the sake of simplicity there is a formula for mm units derived, as it's the most common beam waist diapason: PD(max)=250/d[mm]*Power[W], which has the result in units [W/cm^2]. you have probably seen it in your laser safety course for calculating MPE (haven't attended course myself, but they definitely should talk about it).
So now you should start to see the pattern. To sum up:
If we take multimode LD and increase it's power 2 times, power density increases two times.
If we correct multimode LD FA to make FA divergence 2times lower, PD increases two times.
If we change colli lens of the same LD to make SA and FA divergence 2 times lower, PD increases 4 times.
If we change the source from multi to single mode with the same divergence, aperture waist and power, not only the area of the beam changes (from square to circle, which gives an increase in density 1.27 times), but maxPD increases 2 times because of Gaussian profile of the beam itself.
If we try to determine what specs laser is best (in this case it's 'which rocks best' or 'which should give biggest 'wow''), we simply have to calculate power density in the distance at which we're usually working. For smaller venues you'll find the power contribute more, for big outdoor shows divergence gets its toll, however you can actually calculate it and not simply 'feel' one beam being brighter than another one.
Hope that helps.