Hi, Alex.
It’s a really interesting question, of course. Unfortunately there’s not an easy or simple answer. Well, I guess the closest you could some to a short answer would be: enough images with enough resolution that it works. Then it becomes more a question of how you experimentally go about finding the answers to those questions.
On the resolution question, my guess is that the reason that our “cat” model in Course 1 Week 4 doesn’t generalize very well is not so much the 64 x 64 resolution. It’s really more the fact that the training set is so incredibly small. Here’s a thread which shows some experiments with rearranging the training and test data to see what happens. As a point of comparison, you can take a look at the Kaggle Cats and Dogs dataset. It has 25k entries and they are 32 x 32 resolution images if I remember correctly. I haven’t studied the results of that contest (it’s an old one) to see how good the resulting accuracies are.
The first question is to look around and see if you can find any databases of food images and then to consider how wide you want to make the space of “not hot dog” images. 
There will be more discussion in Course 2 and a lot in Course 3 about what it takes to develop a successful system.