This is a little tricky. We want four easily discernible colors for text, two of them must be reddish and blueish and if they look nice it is a plus.
But furthermore we want colors that will look crisp in smaller text sizes, so we will try to avoid colors that consist of more than two of the CMYK inks. Otherwise you could end up with a slightly blurred result. A print will always be just a little bit out of register, which will show in smaller text sizes.
Let's start out by taking a look at the color wheel (here I use a CMYK wheel, based on CMYK numbers). If we want the maximum contrast it seems logical to choose colors with a 90 degree interval. We need to avoid yellow since it is a lot lighter than the other colors, making it unsuitable for text on white background. Taking all conditions in account we get the following:
The only problem is the green color which is too light (too yellow), so I take the liberty to change it to the one next to it (100, 100, 0, 0), resulting in the following color scheme:
Let's try it out:
I think this color scheme meets your demands, but I am not sure if it is beautiful... Maybe that is one condition too much :-)
If your application doesn't allow CMYK colors you could use these RGB values instead: