It depends on exactly what you want. A focus at a given distance? A beam with as low a divergence as possible? (aka focus on infinity) A beam expander will help you with both.
Although with any laser, you're still going to be limited by the Rayleigh length:
http://en.wikipedia.org/wiki/Rayleigh_length If you really want to go far, you want as high a frequency as possible, so X or Gamma lasers would be best. OTOH, they scatter and absorb quickly in atmosphere, so would be better for space combat. (Same reason the X/Gamma pulse from a nuke heats up the air so fast)
So frequency and the Gaussian beam diameter at it's origin, if you plug them into the Rayleigh formula, you'll see how the beam is better and can go farther, or obtain a better "waist" (focus) in the desired place.
OTOH, I suppose if you fired a sufficiently potent X-ray or Gamma beam, it would partially evacuate the air into a high temperature but low density plasma which may pass the beam better. OTOH, plasmas can also become optically opaque too, so might make it worse. I just dunno... Which are all reasons I'm an IT goon for a software co. that supports people who make this kind of stuff, rather than someone who well.. actually makes that kind of stuff.