I would say it mostly depends on what you're going to use your map for. I usually try to work large, as large as my computer can manage without trouble, just to give the most utility to the map. If you're going to print just remember to set the resolution to about 300 dpi and then set your scale according to the desired size of printing (2400 x 3000 roughly for an 8x10 sheet, fitting nicely on a North American piece of paper).
If your map is ONLY going to be presented digitally then you're golden, since you can get away with lower resolution. You might just have a look at a couple of maps you like here and check their image size, and that will give you an idea of how much detail you can jam in.