Size of Image Textures
The size of the image texture you need depends on a number of things, including:


How close to the camera is the object? The closer it is, the higher the required resolution.
The size of the output render. If you render in high res, you should probably use higher res textures at least for objects close to the camera. If you render in low res, high resolution textures will mostly go to waste as the details won't show on the rendered image.
Type of texture: For instance, if this is an environment map, and you want sharp, clear reflections on glossy materials, you should use a high res environment map for image based lighting. If you don't care about the reflections and just need to get nice lighting and environment colors, you can use a low res, blurry image.
If this texture is used for displacement, normal or color, again it depends on how much detail you need, and this determines the resolution you'll choose for the image.
As you can see I'm not specifying any actual pixel sizes, since as the saying goes, "everything's relative". Your starting point is your render output resolution, and the rest is experience and trial and error.