There are a few approaches, and the 'best' one depends upon the nature of your target community.
Approach one is to use a .dtx file to distribute your class. You can then include and .eps file in the source and have it extract out on unpacking. I've done this in the chemstyle package. Now, you will end up needing to use latex rather than pdflatex in this case, although automatic conversion is available using the auto-pst-pdf package or in TeX Live 2010 with no extra effort.
Approach two is to distribute your files as a ready-to-install 'TDS-style' .zip file. The idea here is that you include everything in a .zip file with the correct folder structure to just unzip in the local texmf folder on the users PC. In that case, you can include both a .eps and .pdf version of the picture. This method is also best for raster images, as you can have a .jpeg for pdflatex and convert it to .eps format for latex users.
The third approach is as you say to use tikz. That avoids needing anything other than the .cls file itself, and keeps things easy to use with latex and pdflatex. The downside is the requirement for a reasonably new distribution. Then again, you might find it better to require something up to date as other packages can also change a lot over the years.
Finally, you could just not worry too much and provide a standard .zip file including the necessary extras. This is often seen with journals. It's then down to the user to put the right files in the right place, but this is probably the easiest and most general approach for you.
As I say, what is best in a given case does to some extent depend on the situation. For example, normally logos are only needed withing organisations. I do a journal class which in the 'real thing' includes a logo, but that is only needed for final printing by the publisher. So the user version just has a space!
You need to enable shell escapes. With MiKTeX you do -enable-write18 and with TeXlive -shell-escape.
You can set up different conversion rules with the epstopdf package
\documentclass{article}
\usepackage{graphicx}
\usepackage{epstopdf}
\epstopdfDeclareGraphicsRule
{.gif}{png}{.png}{convert gif:\SourceFile.\SourceExt png:\OutputFile}
\AppendGraphicsExtensions{.gif}
\begin{document}
\includegraphics{test.gif}
\end{document}
Using epstopdf you can control if the conversion should be done every time you compile or only if the target file is missing.
Best Answer
I would suggest using a tool like "convert" of the ImageMagick package (which is usually installed if you're running Linux, but is also available for Windows).