I wouldn't calibrate based on what the print looks like from them. I'd calibrate to a standard. It's going to be really really hard to find a CRT with good color these days as they basically don't exist anymore and most of what you can find is crappy left overs (those who have good CRTs tend to hold on to them).
If you can find a CRT, programs like Adobe Gamma will do a decent job of letting you calibrate them to a particular white point and get pretty decent results. On the likely chance that you won't be able to find a decent quality CRT, or if you have some money you can invest, getting a good quality S-IPS or S-PVA LCD panel will get the best results.
There are 3 main different types of LCD panels, TN, S-PVA and S-IPS. The vast majority of consumer panels are TN because it is cheaper to manufacture, but it has some serious (critical) drawbacks when doing color work. The color it produces is only 6 bits deep (rather than 8, so it produces 1/4 of the total colors that a better panel can produce) and it also suffers from distortion in the color based on viewing angle. It's easy to see this for yourself if you simply move your head from one side to another while looking at the screen. S-PVA and S-IPS displays on the other hand have much more consistent viewing angles and have true 8 bit color making good panels suitable for fine color work.
I haven't been in the market for a while, but when I was last in the market, you could find a decent 24 inch S-IPS panel for about $650 US. It's probably come down a bit since then since this was about 4 years ago.
Whether you get an LCD or find a decent old CRT, the overall best results will come from using an actual color calibration unit like a DataColor Spyder or similar device. While setting the white point properly is helpful, it doesn't correct for variations within different intensities of the color gamut (the range of possible colors the monitor can produce.) An actual color calibration device will display different intensities of red, green, blue and grey to generate something known as an ICC profile which will adjust the levels across the entire range of intensities.
After you have a calibrated display, you should be able to make color adjustments to an established color standard such as SRGB or Adobe RGB. Double check with your printer to see what color spaces they support to ensure maximum compatibility. Then, when you give them the work, make sure they know that it is properly in a standard color space (and which one) and they should be able to apply their ICC profile for their printer to it, which will adjust the information sent to the printer in order to produce the best rendering of the colors that the printer is capable of producing. (Some adjustments may have to be made depending on the color space of the inks and paper being used.)