Luminous flux of 0603 and 1206 LEDs with the same color and current rating
I think the problem is a lack of understanding of what one means by "brightness". Brightness is a very ambiguous term. First of all, I'll make the assumption that you are speaking in terms of a human's perception of brightness. This limits our discussion to photometry. You have to now differentiate between two measures of brightness, i.e. Luminous intensity and Luminous flux (or Luminous Power). Luminous flux is the  light power emitted in all directions and has SI units of "Lumens". Luminous Intensity is the light power emitted in one solid angle which has SI units of "candela". Think of a solid angle as a cone with it's vertex at the led emitter. You mentioned mcd as units, these are millicandela, so mcd is a measure of Luminous Intensity. You can't directly compare luminous Intensity (candela)) with Luminous Flux (lumens). I did find this tool to convert between the two units, but, it must have to make the assumption that the light is omnidirectional and is only accurate for such lights.

You'll have to get your units straight before you can make sense out of this.

In additon, you have to decide what your objective is. Are you trying to make a light with high luminous Flux or one with high Luminous Intensity? I would imagine that you are going for a light with high luminous Flux or you probably would be speaking of laser diodes instead of LEDs. 

So choose whatever package that maximizes your Luminous Flux, i.e. Lumens. You did not provide enough information to give a better recommendation than this. That is, you did not specify any additional design constraints.