To make experimentation with different map projections, you can use NASA's G projector. It's free and it come with a large number of projections. It can import an image, change the projection and export it. But there is a size limit for exporting the file, so it's best to do it on a rough version of the map. Otherwise you will lose some details. I would recommend doing some tests before getting into the actual mapping as is might be better to do most of the job after converting the map to the right projection.
You can use any software you want as long as you use these file extensions : JPEG, GIF, PNG and BMP. These files are compatible with the software.
- Another more advanced software: Flex projector let you play with the different parameters and you can create your own projection.
The base set of projection is more limited and it's most useful if
you know what you are doing.
For vector based software, the most used are probably Inkscape (free) and Illustrator. They do a great job for planing the world and adding elements but they can't manage textures.
To find a good map projection, you need to know what the map will represent and what is the goal of the map. Some maps are not appropriate to map a whole world and some are not. For example: the azimuthal equidistant projection is good to map poles but not the rest. But most projection can do a good job to represent a world depending on the other criteria.
Minimal distortion: you will need to figure out what you want to keep intact. You can keep the angles/directions (conformal), the shapes, the size and the distance, but not everything at the same time.
- Conformal projection are good for navigation but like the Mercator projection, they all distort the size awfully. It makes Greenland almost as big as Africa. in reality, it is only the size of Algeria.
- Equal area keep the size intact but distort the shape. Here, some of
the most used projections: Hammer, Mollweide, distort the outer parts
of the map. This makes New Zealand look too stretched. All projections in this category try to address this issue but it is not possible to solve it.
- Equidistant : The equirectangular projection is widely used in amateur map making because it is the simplest.
As smithkm pointed out:
An equidistant projection preserves distances toward or away from a
particular point and its antopode. In polar aspect azimuthal or normal
aspect cylindrical/conic these two points will be the poles in which
case it preserves distances along meridians rather than between them.
In such a case the distance between parallels will be the same,
because they are equally spaced north to south.
- Compromise projections: these projections try to minimize the total distortion by accepting some distortions on the size, shape, or conformity. In this regard, they might be the best for someone trying to minimize distortion without working on a globe. A globe would have no distortion but it requires a 3D software.
National Geographic have used these projections for more than 100 years. Including: Van der Grinten, Robinson and now Winkel tripel. They have the advantage to look more round and natural than other projections. It is more eye pleasing but they still are distorted in some ways.