Most if not all versions are viable, but Adobe offers Photoshop CS2 on their website for free, and that's what I'm using at least. You don't really need a powerful computer or anything (mine's a crappy $250 laptop lmao) so I'd recommend starting there. Another thing is that most of the templates are in .psd format, which is basically the Photoshop file format, and while there are plugins for Paint.net and Gimp to open these, I've heard that they have things missing something.
As for the others, I haven't tried Gimp and with Paint.net I did a few Mega Drive covers but since there aren't any lines that your image can snap to or anything, looking back with the spine the game logo would often go outside the area.
So all in all, it's up to you, though I'd definitely recommend Photoshop. They are all free though, so just try each one out and see what best suits you.