PNG and EPS are lossless, so they can not look fuzzier than before, unless you resize then or use a crappy encoder.
With any other type, it heavily depends on the tool. Old Photoshop CS2 used to make high quality JPGs even on quality level 7, new Photoshop CS6 does not even make nice JPGs on level 9.
Best is to use lossless graphics and the right color space (RGB or CMYK) and color depth. Perhaps 1 bit will do for you.
Can you give an example of the fuzzy result?
Using text in graphics is something I would be avoiding in this day of Typekit and CSS3 which allows just about anything on the web. That said, do not use InDesign for this. If you already did, then export to PDF, open that in Photoshop and create the graphic there.
Remember that Facebook and others will introduce their own compression on any submitted art ao it can be a real crapshoot.