What about the users? ;)
A directory by nature should have a clear and easy to navigate structure (taxonomy). I think planning the structure in the most logical way is 98% of the "fun" of directories. It's what makes your directory stand out among the rest (whether good or bad). I would NEVER let submitters dictate either the taxonomy (including category names) or the listing "title" format or descriptions. A good editor can write a description to a listing much better than 99% of the site/listing owners. As long as you start out or rectify so every listing is created equally (using the same format) people are usually more than happy when you end up using 1% of what they actually submitted.
After re-reading the OP, the easiest way to create subcategories is on a "need" basis.
Example: Say you have a Topical category Shopping and under that one of your main categories is Furniture. After a while that category might contain either one long page or a few pages (depending on how you are displaying them) of dozens of Furniture stores. It is then logical and "user friendly" to start breaking this down into subcategories as you may notice you have 5 or 6 listings that specialize in Outdoor furniture and another 5 or 6 for Dining room furniture. You simply create the categories Dining Room and Outdoor under Furniture. You then have a taxonomy of Furniture>>Dining Room and Furniture>>Outdoor. Very simple thought process and it is the same process in use at dmoz etc. In the end, you may end up with nothing listed directly in Shopping>>Furniture and that's OK ;)
[edited by: The_Contractor at 9:19 pm (utc) on July 31, 2007]