- I would draw big and scale down.
- I would use a canvas size of 800 x 800.
- I would use big round brushes for that cartoon look. Using vector art is another possibility (you can use Inkscape for that, it's an incredible freeware tool).
You can pick any canvas size, just as long as it's not too small a size that you start painting in pixel-art directly, nor too big so that you're over-painting detail that will be lost when scaled down.
Prefer sizes that are your original size, doubled one or more times (in other words, your original size multiplied by a power of 2).
That is, if your target size is 100 x 100, pick a canvas size that is 100 times 2, 4, 8 or 16 for instance. I'm not sure if I'm on the right direction here, but I suspect you won't lose excessive detail if you stick to powers of 2.
- - - - -
As another example, say my target size is 67 x 67. I would pick a canvas with a size of 67 doubled one or more times.
67 x 2 = 134
134 x 2 = 268
268 x 2 = 536
536 is a comfortable canvas size to paint, and when scaled down back to 67 x 67 it won't lose detail. That is, it will lose detail of course since there's entropy, but certainly much less than if you were using any random size, like a prime number size for instance.
EDIT: In hindsight, it's not about detail - which you will always lose when scaling down from a bigger size. But it's about the consistency of the resulting graphic. If you scale down from a size that's doubled one or more times, the detail you lose will be "consistent" since the bigger canvas can be "divided" back to the smaller one. If you pick a randomly sized canvas - worst case scenario a prime-number sized canvas - the resulting graphic may appear distorted in certain parts where the division isn't exact.
It might be too subtle, but every pixel counts at these sizes. I wouldn't find strange if you had to touch up the resulting graphic on a pixel level later on, just to make sure it communicates what you want (i.e some important, small detail that was lost during the scaling down).