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.

LEDs come in all sorts of brightnesses and viewing angles.

Within some limits, the brightness of the LED is proportional to the current flowing through it, though this relationship is far fron linear.

The amount of current transformed into light is a measure of the LEDs efficiency.

If you want a set of coloured LEDs to match, then examining the manufacturers datasheet is a good start. Also make sure you take into account the viewing angle. Although not strictly true, half the viewing angle results in about four times as bright for the same power and effeciency.

Select LEDs with the same brightness at similar currents and identical viewing angles.

Lastly remember the human eye responds really badly to deep red and deep blue colours (see Wikipedia) so the aparent relative brightness between different coloured lights is somewhat subjective.

I should have included that LEDs are current devices, not voltage. The voltage across (Vf) them is variable between samples and over temperature. (remember LEDs get hot). This means high power ones should be driven by a constant current circuit.

I had this problem once matching brightness between green and red LEDs. I put the red LEDs on a pwm pin and then used a pot to change its brightness. Use the serial connection so you can see the value of the pot as you tune the brightness. Once you find the level of brightness you want, take the value displayed in the serial connection and hardcode it. Then remove the pot (and its associated code) and you are good to go.