The rule is that a pixel in a texture (texel) should be no bigger than one pixel in the output. So it depends on your scene: foreground objects have bigger textures and background objects smaller.
For good results, calculate approximatly 1 pixel of the texture or more per pixel of rendering. If your texture takes half of the space in both direction in a 1024 x 768 render, than a good resolution for a texture would be 512 x 384 or more.