Ok, here were the options I'd considered. Once I decided to go with the "Gavin a Blast" option, I stopped working on the others so they are pretty much first drafts. I'm no artist, but I was pleased with the end results.
I know I recommended Paint Shop Pro, but I got to thinking - if you're a Linux user, you could probably use the Gimp to produce something similar, and that's free software (and actually, I think it's also been ported over to the Windows platform).