I made a plugin today. It functions like a tag cloud but it uses the number of articles and categories inside a category for its weighting. Since that is in an optimized database table, it should run very quickly. The plugin itself takes a single category name. Every sub-category under that is considered a single tag, with the size changing based on the relative size of each other. You can see a larger variant at userscripts.org. If you have a del.icio.us account, you can also find another one. At the moment, the one on brokentypewriterpress.com is pretty damn sad, but I'm hoping things will bulk out so it looks prettier.
I'll probably iron it out a bit more, add some nifty features, then post it up on the MediaWiki extensions page.