To your first question: I usually set my canvas size to my desired final output size. Lately, I have been displaying my maps on an HDTV, and I have not needed the ability to pan around on them, so I have been designing at 1920 x 1080, the native resolution of my television. When I designed a poster map, I knew my final output was going to be 32" x 24", and I wanted 200 dpi, so I started at 6400 x 4800. (Desired physical size multiplied by desired print resolution will yield pixel dimensions.) The type of map doesn't really matter to me at this point. I can make a poster-sized continent map or a page-sized battlemat, or vice versa.
Scale is a somewhat more involved discussion. If you're making a battlemat for D&D, or another game that uses similar rules, the convention is that each 1 inch square represents a 5-foot square. If you want to print the battlemat at 150 dpi, then 5 feet = 1 inch = 150 pixels. If you never intend to print, then you can drop any reference to dpi and inches, and just say 5 feet = 150 pixels. Or 100 pixels, or whatever you think will work best for you.
Sometimes scale is dictated by other limitations, such as the time I was working on modeling the Nazca plateau in Peru. I had a height map with a resolution of 3 meters per pixel, and that was the smallest I could go without having to generate artificial detail. I eventually abandoned that project, although I hope to return to it at some point.
And sometimes scale is relatively arbitrary: divide your map's logical width (300 miles) by the image's width (1200 pixels) to get its scale (.25 miles per pixel).
Now, the second question is fairly straightforward. My advice is to make your brushes roughly 2 - 4 times larger than you intend to use them. Never scale up if you can help it, because that will cause softening. Theoretically, you can make the icon or brush as large as you please, but it's easier to design closer to your usage size so that you have some idea of what kinds of details will be visible when you actually use the brush. And, the smaller you go, the more you risk filtering doing something unexpected. Check out Redrobes' article on bitmapped images for some details on that. His illustration with the zebra is particularly relevant.