Jon,
I think the best approach for this is to clone the tag cloud webpart and during the rendering of each item you'd have to perform your formatting per tag. You could create a binding/linking table that has a tag bound with a style. Then when rendering you can apply it based on the lookup you find. I've done similar with the tag cloud webpart before and creating friendly urls vs. url ID parameters.