Can someone recomned me a program that can edit flcs.

Use Flicster, and Paint Shop pro.

Or Civ3 flic edit. Once you export the flc as a storyboard you can edit it with quite a few paint programs. It depends though exactly what you want to edit.

Problem I have in this case - other than my complete lack of any graphical skill - is that in PSP's Animation Shop, whenever I save it does that strange thing about file size and quality, and the game can't read it after if mucks about with it.

You can use Animation Shop only for "simple" flc-files (in civ3's case: leaderhead flc's).

The unit flc is a special kind of file, which has eight different animations (you guessed it - the eight different directions unit can face) instead of just one animation. To edit these files you need flicster or Civ3flc. You can look them up in the utilities subforum here.