Tiles or one big bitmap? If you are going for free stuff then check out the gimp. (psp might be free aswell, not sure) If you have a couple hundred to spare then grab adobe photoshop.

What kind of art program should be used to create maps for RTS games?

------------------

If your going with one big bitmap you can get some great terran,ect from rendering in 3dsmax(though its high $$$). Im rendering all my art for my game im working on currently ,and it looks great.