Are either a Multiplexer or Decoder going to help me with this circuit design?
I don't completely understand but you can implement any 4 input function in a 16 to 1 multiplexer.  Say for example you use a 74150 with select inputs A,B,C,D.  You could put A=X0, B=X1, C=Y0, and D=Y1.  Then you just pull up or ground the corresponding inputs.  So for example if you input DCBA=1001, so Y>X output 9 would be 1 for CO.  A second chip would do C1.  When you connect the multiplexer like this you are actually building a 16x1 ROM.  That should help you with your bigger input vectors.  I'm wondering what you are going to do when X=Y?  Except for what happens when the inputs are equal, it looks like C1 is the inverse of C0.  That would save you the second multiplexer.