To get rid of the aliasing that's bothering you, create a normalmap that is at least as big as the screen. As with every other texture the normalmap will be blurry and have artifacts if it's scaled up beyond it's initial width and height.

Ideally you would also not create a square normalmap, but a 4:3, 16:9 or 16:10, depending on you resolution. That way the pixel aspect ratio will always be correct and you won't get any refracting artifacts in your map

So for a screen res of 1024x768, create a normalmap that is at least 1024x768 in size. As long as it has the same aspect ratio it should work just fine.