Dennis, Doorknob, Martin Büttner, Chris Jester-Young - Pizzeria!
CJam, 20 bytes

q~1$*4/"CEDM"e*/:$N*


I think this should work :)

Try it online

Explanation:

This first makes a pizza labeled CC…EE…DD…MM… from left to right and top to bottom, then sorts each row in alphabetical order. The only disconnections can happen between the C-E border and E-D border, or E-D border and D-M border (if they fall on adjacent rows). But the sorting ensures that the E's go to the right side and the D's go to the left side, as C&lt;E&gt;D&lt;M, so the E's and the D's remain connected.

q~          read and evaluate the input
1$          copy the width
*4/         multiply with the height and divide by 4
"CEDM"e*    repeat each letter in "CEDM" that many times
/           split into rows of the given width
:$          sort each row
N*          join with newlines