The best you'll be able to get with the formats they support is likely to be via PDF or possibly PostScript (.PS) format.
PDF supports both vector and bitmap images so as long as the program you are using has a good PDF exporter then the quality should be nearly identical to the original.
You can check this by exporting to PDF and then opening the file, when you zoom in a large amount you should see lines initially pixelated but they should then re-render and have the same smooth edges as they did at lower zooms.
PS format is a format intended for printing and also handles vector art as well as bitmap images and was originally intended to be used on plotter printers (I believe). I don't have any real experience using this format except to know that it is often natively supported by high quality printer devices and can allow you to poke a file you have directly to the printer rather than trusting the system print spooler and drivers to convert your file appropriately.
Either of those formats should do what you want, but PostScript might be closer to what they expect to send to the printer.
Of course even if you send them a vector image there is a chance that someone in the chain might convert it to a bitmap format for you, but you would hope this was not the case.