You say you want links to categories and to products - which is it? Do the categories have more than one product each?

Replacing sidebox headings with images will not help you here.
You can use Categories Dressing and replace the category names with images by following its directions.