The best resolution to start an image of 500x500px is... 500x500px.
I have the feeling that you want to reinvent the wheel or something. But lets explore the matter a bit.
Any resampling or resizing of an image means it has some manipulation on the data. This not always means "loos of quality" but it implies manipulation of the information, the information carried by each pixel is somehow manipulated.
Depending on the type of image, a graph, a vector drawing, an heraldic shield or a modern simple logo, a photo of a gothic cathedral or a photo of a 70's furniture... it can react good or not so good to this change in information.
Another factor is your source device, if you have a camera of 24Mpx to take your picture, the best resolution would be... taking the original photo at 24Mpx.
The neverending recommendation. If you can make an image in vector format, do it, if you have a decent camera that takes nice pictures, use it.
A couple of specific recommendation I would make. If you are going to make a digital paint, do it about the same size of a 24Mpx photo, 6000x4000px. You will not have a slow monster to work with, but at the same time, you have a good size to resample to whatever size you want.
Of course, resampling it to 500x500px will need a crop and you will lose a lot of details, but you have your original with you, probably that 500x500px image is only a thumbnail.
There are times where the antialiasing system of the program where you are creating the image is not the best one. For example, a render engine of a 3D program can render some noise, or the aliasing of diagonal lines on the exported vector logo can look like a saw. In those cases go to the simplest formula. Make it twice as big, so generate a 1000x1000px image. Now you can play with the settings of your raster program, use a bicubic, sharpen it or whatever you want.