I am creating textures for HL?, too and I know this problem very well.
HL? usually compresses textures with the DXTn method.
Basics of DXTn: it splits the texture into 4*4 pixel blocks, then stores two reference colors for each block (2*16bit) so that each pixel of a block can mix its color from those two (16*2bit), that way you'll have 64bits for each block, which is quite a good ratio.
For normalmaps though, this compression method is rather useless and often causes entire blocks to have the same color, which makes them appear blocky.
Solution: do not compress normalmaps, or make them larger. Both will increase the filesize, the latter however might also make the texture cause longer rendering times.
For each normalmap, you'll have to decide, which is more important: size or beauty. In general, very smooth normalmaps should not be compresses, while noisy normalmaps hardly suffer from DXTn compression.
For HL? texture conversion and viewing, I strongly advise using
VTFEdit.
It is the most advanced application for creating HL? textures and lets you easily control all propertires of a .vtf.