*Any* program you choose will have just under 8 gazzilion tutorials online, so don't worry about that. Plus most of the programs do the same stuff anyhow, so it's just a matter of finding that particular "tool" and you can do it in other programs as well.
I use PaintShop Pro, Photoshop, and Illustrator. I usually design in PSP, add a touch of Illustrator and then compile all the different layers in Photoshop. Photoshop seems to handle large files like saideart & 4-player cpo's better than PSP does.
The first thing you'll want to learn is the value of working in different layers. For our cpo's, I'll have anywhere from 5-15 layers. It make stuff easy to edit, select/mask and delete. If you get into 5+ layers on a marquee size project, Photoshop will probably be better, but it has a little steeper learning curve. Illustrator is probably the hardest for a beginner to use.