Why are red LEDs so dim & how do I make them brighter?
It is highly likely that your red LEds are of lower luminous effiiency than your white LEDs. 

Also, driving an LED incorrectly can destroy it or reduce it's output from then on. Such damage can occur almost instantaneously. Red LEDs have lower operating voltages than White LEDs so are more likely to be damaged by the application of a constant voltage that is too high and not current limited. 

The efficiency of LEDs varies widely.
 It can be expressed in lumens/Watt = l/W.
 The best White and the best red LEDs have similar enough l/W ratings that both should appear about equally bright when driven with the same power input. White LEDs typically have operating  voltages = Vf  in the 3.0 - 3.6V range and red LEDs have Vf = 2.0 to 2.5 Volts. So a red LED would need about 50% more current to achieve the same power as a White LED as Power = V x I.

You state the LED output range as 500 - 20,000 mCd. That's a 40:1 brightness range.

Note that candela are a measure both of energy out and area of illumination. Less area = more brightness for the same light energy.