When you get the Save As window, after selecting Save As EPS, click on the settings & then transparency.
See where the Raster/Vector slide is. Try moving it to at least 75% vector. You can also try increasing the resolution in the rasterization settings.
If these are pdfs that you make, try changing the settings to be compatible with Acrobat 5 or higher and save in at least a prepress quality. A lot of the default setting supplied with Distiller or the pdf export function in Adobe apps sets the output to be compatible with 4. 5 and higher have better transparency support.