Problem solved, but in a roundabout way:
(This also solved my cats as headings, sub-cats as links issue - http://wordpress.org/support/10/2373)
I'm not displaying my categories at all. Instead, I simply set up a link category to match each category. Then, I create a link for each sub-category and assign it to the proper link cateogory. The uri of the link will include the category id and sort information.
For example, if I have a sub-category of "Italian" in the category of "Region", I create the following link:
Then, I simply use get_links_list() in place of list_cats(), and I've killed two birds with one stone! Since I'm not using any outside links at this point, get_links_list() will work just fine. If I decide later to add links, it'll simply be a matter of building my fake "category" section using get_linksbyname, then building the "links" section somewhere else using the same method.
Wish there was another way, but I'll take it.