Pretty much what copespeak said. I would recommend between 1000-2000 for a good balance between brush size and speed (usability) and the amount of detail you can add. You do not have to worry about printable size because of the scripts, so you do have a lot more flexibility than normal.

Note: While scripts work great 99% of the time, you will start to see some differences if you make a very large size jump (e.g. from 500 pixels to 5000 pixels) and you like to use the very thick texture tools (e.g. oils, paint tube). This is because the depth (/height) off the canvas is limited, so they will get relatively less textured as the size increases. This will only matter if your work depends heavily on thick paint texture, but the larger your original image, the less drastic the change will be.

But you'll be able to run test scripts, and just replay them at different sizes easily, so you will be able to figure out the sweet spot for your style.