Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?
This may sound counter intuitive but one of the biggest rules of thumb for model capacity in deep learning:

IT SHOULD OVERFIT. 

Once you get a model to overfit, its easier to experiment with regularizations, module replacements, etc. But in general, it gives you a good starting ground.