First, I love what you've done so far, and that you are so active in the progression & updating of this news script! I've had some ideas to enhance categories that I think most people would enjoy & appreciate:

Images for Categories: Have each category have its own icon/image that can be displayed using a tag similar to {avatar} in the news template. Multiple categories would display multiple images.

Category Cloud: Some sort of script that would display categories with font sizes equal to percentages of posts in the category. Example here: http://utilitees.de/ee.php/category-cloud