Batteryspace.com sells packs, I think prices are reasonable, but I'm no expert. Digikey.com also makes custom packs, but they aren't cheap.
There's only one size of C cell. If it's not that size, it's not a C cell, but maybe a sub-C, 26650, etc. Currently, C cell capacities are in the 4.5-5 A-H range.
You'll need to know the configuration of the cells, as there are many ways a 20-cell pack could be laid out, and some will fit in the canister and some will not.
If you are going to fast charge (anything faster than a 'standard' charge of 16 hours at C/10), you should have a temperature sensor that's matched to the charger, and it's best not to charge in an enclosed environment. Overcharged cells produce hydrogen gas which could be an explosion hazard. Most modern cells will re-absorb the gas during a standard charge, but they can't always keep up during fast charge. The temperature is used to help determine when the charge is complete. If the old pack has something unknown in it, it's probably that and it should be transferred to the new pack.
Yes it probably is wise to charge the 2 parallel packs individually. NiMh does not seem to like parallel charging of cells.
As DIW said its best to rebuild the existing pack by replacing the cells than just make up a new pack. That way you keep the items like thermal fuses and the like.
Or just build a LI Ion pack of the same voltage range.
+1 for Battery space. ( If only they would get their act together and offer reasonable priced international shipping.)