With polygonal objects you should map the UVs so that a square checker texture doesn't show any kind of stretching or distortion. After that what ever square texture you map on it should be alright. Why square? Well, it comes from the 0,0 - 1,1 UV area being square in nature. That said you should make your textures square too.

So if you have a texture file which is 256 x 512, it is better to increase the image canvas size to 512 x 512 than to try and correct the stretching some other way. That said it is also a good idea to try and layout the UVs so that there is minimum amount of empty space in the 0,0 - 1,1 area.

I remember reading somewhere that square file textures are even faster than non-square ones because Maya will handle all textures as squares anyway...

Nurbs have built-in UVs which you can't modify. Sometimes turning on the "Fix Texture Wrap" attribute in the shape node helps. Rebuilding the nurbs surfaces to as uniform as possible also helps...