When you say "CMYK version just sucks...", what do you mean? Are you referring to your screen's view? Have you printed the logo? What profile do you have assigned to the RGB? Typically when converted from RGB, CMYK will appear dull, but prints bright ( depending on paper and printer used ). The other option would be to assign pantone spot colors to each of the elements and have that printed offset, but I get a sense you're not talking that far along. I assume the logo was created using RGB color space in Illustrator? Otherwise, there should already be a decent CMYK file created, along with a spot color version, along with an RGB version.
The bottom line is that you're never going to get anywhere near those colors on press when you're printing with standard four color inksets. You can get pretty close to the red, but the blue and especially the magenta are way out of the gamut of the inks used in offset presses. Your choices are either to print the closest CMYK equivalent and learn to love your new muted palette, or to pony up for what are called Spot Colors, which are typically spec'd in Illustrator or InDesign and taken from something called a Pantone swatch book. The printer then prints those colors with specific Pantone inks that will match (or very close to it) the colors printed in the Pantone swatch booklet.
This is a very common rookie mistake when inexperienced designers design something that might look great on screen but have no clue that printing inks simply can't print most of the brighter, more saturated colors. Logos are either spec'd with printable CMYK equivalents or with actual Pantone ink colors.
Printing this with three Pantone colors is certainly doable, but is going to be more expensive than a standard printing. Talk to your designer about redesigning or at least re-spec'ing the logo and talk to your printer about how to go about a custom Pantone print job.