Why do these LEDs have different brightnesses
This is going to be really long, so just skip to the summary sentence at the end to avoid TL;DR.



There are several factors contributing to varying millicandela ratings of LEDs, and more importantly the relevance of the mcd rating to the intended purpose:


Angle of dispersion / beam angle:

This one is the most obvious, and fairly intuitive as has been pointed out in user20264's answer. The narrower the beam angle (how far off the axis the LED's light is visible) the greater the luminous intensity for a given luminous flux: Basically the same amount of energy being pushed through a greater or smaller solid-angle. 

Paraphrasing Wikipedia, a light source emits one candela in a given direction if it emits monochromatic green light with a frequency of 540 THz (555 nm wavelength, yellow-green), with a radiant intensity of 1/683 watts per steradian in said direction.

 (source)

This is why illumination grade LEDs are often rated in lumens rather than mCd, as the MCD can be quite misleading depending on added elements (lenses, diffusers, reflectors) that would change the effective beam angle, by definition.
Practical measurement of "peak luminous intensity": 

While peak luminous intensity is supposed to be measured as a single point, on-axis value, there is no global standard for the geometry and size of this "point" sensor:  

Is it 1 degree around the axis, 0.01 sq.mm, square bare-wafer photosensor / PIN Photodiode, circular lensed sensor (if so, what diameter lens?), half-theta angle (yes, some scientific papers use this as a measurement area), or something else entirely? Is the distance to the sensor measured from the LED package surface, the wafer surface, or the LED lens inner or outer surface?

You will find nearly as many answers as there are manufacturers, and clearly, keeping this flexible allows for some "creative accounting", to favor one type of LED versus another.
Geometry of lens:

The specific optical arrangement used for the LED lens will change the distribution of light intensity across the illumination beam angle - One can get very intense light at the center of the beam and a long tail of fall-off, or fairly even distribution of the intensity between axis and maximum viewable angle, just like with camera optics.

This impacts the "half-theta" angle, the angle at which intensity falls off to half that at the axis. Depending on the lens and thus the intensity distribution curve, half theta angles can be a small fraction of beam angle (center-intense beams), or heading towards half the beam angle or more.

A smaller half-theta angle i.e. a skinny tall bell-curve with long tails, translates to high mcd values on the axis, but sharp drop-off of visibility off the axis. For greater range, such as for infrared remote controls, a smaller half-theta is of interest, while for visual indicator / illumination needs, a greater half-theta works out better, even for a fixed beam angle.
Angle of view:

This relates closely to the previous two points:
If the half-theta or beam angles are narrow, the mcd figures can look very high, but practical usability of the LED as an indicator by itself is questionable. Yet, if a light-pipe is used, such as on some indicator boards, or for fiber optics, a narrow half-theta is a good thing.
Transmission coefficient of lens

This relates to the specific light wavelength emitted by an LED:  

Manufacturers typically standardize on one or a very small number of materials for the design of the lens element of their LEDs. Evidently, any given transparent material will have different transmission characteristics for different light wavelengths. 

Thus, what may be the best possible lens material for a green LED would likely be less than ideal for red.  

For white, this is even more complex, because common "white" LEDs have a phosphor layer of Yttrium Aluminum Garnet on a Gallium Nitride chip emitting a deep blue spectral line. The combination of the natural and the phosphorescence spectral lines requires compromises in transmission and phase, so the combination is anything but ideal in transmission for each spectral line, by the nature of the optical design.
Clear v/s translucent LEDs:

Milky LEDs make the mcd ratings practically irrelevant, since they are designed to disperse the generated light as evenly as possible across the surface of the LED - near-180 degree (or should it be, near 90 degree?) solid angles, and half-theta values of nearly the same, are common, and desirable.  

Thus, a milky LED will typically have poor mcd values for the same chemistry and construction as a "water-clear" LED, and colored clear LEDs will lie somewhere in the middle. Yet, for indication purposes a translucent LED is perhaps the most ideal!
Wavelength of emitted light
As would be seen from the definitions of luminous intensity, this differs from radiant intensity in taking into account human-vision perceived intensity of the light in question. 
Human beings characteristically are most sensitive to the yellow-green portion of the spectrum, around 555 nanometer wavelength:

(Source is Wikipedia, high resolution image here)

Thus, for a given amount of electrical power through an LED, the luminous intensity would vary widely with LED color, and of course drops down to zero for ultraviolet and infrared, which human vision cannot perceive.
Chemistry of LED junction:

Enough has been written about this, in other answers as well as elsewhere on the web, so just a brief mention: The chemistry determines the emitted color-spectrum (see previous point), as well as the conversion efficiency, of an LED's "Light Emitting" aspect. Also, minor variations cause spectral shifts, so two nominally identical chemistries need not be. It is thus stating the obvious that this determines both luminous flux and intensity.
Efficiency of wafer / batch:

Despite the best manufacturing process controls, LED manufacture is notorious for its variation in efficiency and output characteristics between batches of wafers, and even within a batch or a single wafer. Manufacturers address this by a process of "binning" - While white LEDs are binned by a complex process, by color as well as light output, color LEDs go through an essentially linear binning process for light output. Different light output levels are then packaged as differently rated products.

While reputable manufacturers typically do a sincere job of binning and published rating for their LEDs, no-name LEDs are infamous for wide variation in intensity within a stated datasheet rating, as much as 1:3 ratios in extreme cases. 

n.b. Some manufacturers such as Philips (Luxeon range) are beginning to claim a binning-free process, due to modern improvements in manufacturing technique.
Encapsulation of LED:

While this is largely covered in the lens design discussion a few points previously, additional factors such as position of contact whisker / wire bond do make significant impact in LED light output. The wire bond creates occlusion of the light source, the nature of which varies between designs.

An obvious response to this would be, why not always design the wire bonds to occlude as little as possible? This isn't done because the wire bond positioning, material and thickness are not just about electrical conduction, but also thermal dissipation. 

Some designs need better cooling, hence a whisker attached to the approximate middle of the chip, or even multiple wire bonds from a lead-frame, are opted for. Other designs do not really care about this, the power involved being too low or the substrate being better designed for thermal off-take. 

These trade-offs determine the occlusion compromises and thus the actual measured luminous intensity at the axis of the LED's beam.
Orientation of LED substrate within package

This factor has little relevance to most modern LEDs, especially SMD parts. However, older LED designs, and possibly some still in production, sometimes had orientation tolerance issues on the LED emission surface. In simple terms, the actual LED chip may or may not be perfectly perpendicular to the axis of the LED package. 

It is intuitive therefore that measured luminous intensity along the axis would vary from piece to piece, or between production runs, for such LEDs.
Actual power of LED:

While the rated current of an LED is typically controlled by your circuit to meet the datasheet specifications, the rated and actual junction voltages at that set current will invariably differ, both due to manufacturing tolerances, and due to shortcuts taken in datasheet specifications.
This means that the actual power converted from electricity to light will vary as per P = V x I, for each LED design, for each minor variation in semiconductor doping, and for a variety of other factors. Part of this is addressed by the binning process, and partly the datasheets for "different LED models" which just happen to be different batches of wafers, reflect the resultant change in measured intensity.
Most important, marketing mumbo-jumbo:

While this fudge-factor is perhaps the least recognized by the engineering community, several years of using and recommending LEDs for various products has shown that there is a very strong influence the marketing department of a manufacturer has upon the data shown in promotional materials and datasheets for a given LED product. This is probably more pronounced in the LED industry than in most other semiconductor trades. 

If there are several different ways of measuring or representing any LED data, such as luminous intensity, and there are several standards or guidelines in place in the industry for any such parameter, you can be sure that the marketing drivers will ensure that different product lines or models will use different measures and measurement methodologies, even within a single manufacturer, so as to put the best possible spin on every LED. 

While the more reputable manufacturers may stick to merely using different intensity measurement equipment as convenient, the less scrupulous ones do not shy away from outright prevarication for their product publications. 


What makes this more amusing is that some of the most reputable manufacturers are also resellers, i.e. they source their non-premium product lines from the same factories as bulk sellers, so the only difference is the branding on the box or reel, and of course the 100% to 300% brand-value mark-up. How many of these resellers actually bother to re-validate the measurements and parameters, is anyone's guess.



TL;DR summary:

Don't trust the millicandela ratings on any LED, test them yourself if you absolutely need real data.