So lets just say I have a set of flat colored animals and that each texture is around 16x4. Is vertex painting more optimized?
Vertex painting can have issues where you need additional loops or split edges to prevent colors interpolating over faces (i.e. bleeding/blending), but it saves you requiring a texture and you can use any color. However, if all of your models use the same color palette, you can do this with just one texture, and the difference between using either-or is negligible, perhaps even in favor of the texture approach because you no longer need extra polygons to keep edges between colors sharp, or extra disconnected vertices, and you only need to download a single likely very small texture.
You could alternatively combine both, allowing you to use vertex colors to shade your color palette (by using dark vertex colors) without taking up space on your palette. It doesn’t look like this fits with your art style though.
In the grand scheme though it doesn’t really matter. You may see a very very small gain in rendering performance going with vertex colors because the GPU does not need to go through UV mapping for the texture, but this is likely an extremely small difference on any half modern device. You’ll have problems with lag due to the sheer number of instances long before you have problems due to using textures.