I don't know if this sounds sketchy to you, but I have had good experiences with this online service so far:
http://www.zamzar.com/convert/gif-to-pcx/I know in some old tutorials Bazz mentions Jasc Paint Shop Pro. I remember this being a popular program in the early 2000s, and I think it is still floating around olderversion.com
I use photoshop to create the images and then make it a gif because it uses some kind of palette and you can control the number of entries in the "save for web" dialog. You can't really move palette entries around individually, but you can order by frequency, luminosity, etc.
Do NOT try to create PCX files with photoshop though. At least in CS6, (the latest version is CC and gets frequent updates because it is "cloud-based" so they may have fixed this), if you save a PCX the palette entries will be "backwards". That is entry 0 will be entry 255...and so on. I'm not sure why this is and no attempt to "invert" the palette in photoshop would work correctly. I know other people have experienced this but it was on a forum for customizing some RPG, not SNES related.
The only way I was able to fix this was with the GUI-d version of pcx2snes, which was actually great because you can move the palette entries wherever you want and change their individual values. However this only really works as far as the GUI/windowed version of pcx2snes with "background images" it assumes 8x8 and 16x16 tiles, so when I tried 32x32 or 64x64 tiles for sprites, I got results that weren't what I was expecting. That being said I haven't mucked around with how the SNES stores tile data, so it may be fixable in some way I am not clear about. (pcx2snes is also obviously designed to output snes tile data, not to "fix" pcx files)
(apologies on the verbosity, but thought it might be helpful)