Try OBJ, and if that has trouble, then get MeshLab (free) to convert it to something they like. They might want STL or another format.
As for their comment about it being triangles, the only thing I can think is they were expecting a file with primitives and boolean solids operations, (sphere, cube, cylinder) instead of a mesh. DXF is totally capable of that, but Carrara is not. It doesn’t really use those internally, so it certainly can’t export to it. That would be a task for Autocad or Solidworks. 
But there are tools to create a G-Code tool path from a mesh. MetaVector is one, (I hadn’t heard of- interesting) or try Skeinforge.
Skeinforge is open source, and originally for 3D printers, but also has a cutting mode for CNC tooling.
It looks to me (in a brief peek) that MetaVector is designed for 2D designs - it mentions several CNC type tools that are typically used only on flat stock. (sheets or plates) Skeinforge is designed for full 3D work. Not knowing anything about your task, I can’t say which is best for you.
One possibility is the company is only expecting 2D lines, instead of a 3D mesh. If their CNC tool is just a cutter then it won’t have much height control, and they may use it primarily for signs or sheet metal. But even in that case, if it reads G-Code it can be used with Skeinforge to do 3D. (Within it’s limited height.) But if it read HPGL or some proprietary language, then there’s not much it can do with height.