the size doesn't matter so much as does the texture that you are applying to the skybox (at least so long as its bigger than your playspace, there are apps out in the wild that will help you create skybox textures with seamless edges. If you are looking to use procedural generation your skybox, you have to do some flat to spherical projection so that as you fill the pixels, they appear to to have information from the correct direction.. I was working on a skybox for a space game using perlin noise and other techniques to get nebular clouds and stars sprinkled over the skybox, so just using the 3D coordinates of the pixel on the plane wasnt enough to pass to the noise functions, I had to treat that 3D coord on the skybox plane as a direction vector, then normalize it before passing it to the noise function (essentially putting the point on the surface of a unit sphere before using it to figure out what the pixel color shoudl be)... that fixed the projection problem and eliminated all visible edges in the skybox.
There is a skybox generator for Blender, an app called SpaceScape, and a FilterForge plugin for photoshop to help with creating skyboxes... I'm sure all of them do something along the lines of what I had to do for my procedural skybox generator.