1) Even Photoshop may fail to produce standard EPS file! Trust me or not, the standard EPS format is only a proper subset of PS, and Photoshop (a product of Adobe itself who's the patent holder for PS/EPS formats) doesn't do a good enough job. An alternative that I always use (on Windows, of course), is to install AdobePS drivers (downloadable from Adobe site for free) and set the printer's target to FILE: port, and its output PS format to be "Encapsulated PS" (must modify this manually, or else it will produce non-standard format again). So you can print your graphs/figures to this printer, and get a .prn (or .ps format). Use Ghostscript (+ GSview for GUI) to convert this .prn/.ps file to .eps and automatically compute the bounding box.

2) To get clear picture in double-column mode, there are four points to take note:
a) Try not to draw high-resolution graphics/figures as the source. If you have to do so, use larger types and thicker lines.
b) For graph plotting (line/bar graph), I recommend gnuplot, which produces much better looking graphs when using with LaTeX. It can also produce PS+LaTeX output so that the fonts in your graph can be actually LaTeX typesetted, thus without the problem of scaled fonts.
c) Scale the graph using LaTeX's argument (graphx package and dvips driver are highly recommended) instead of using external graphics software.
d) If your figure/graph is really big, try to use single-column floats in your double-column document.