I hacked around with WordPress until I found this solution...
I set up my Categories to be in different directories, with different indexes.
What I needed was, for every link generated by the_category to link to the category directory I created. To make things simple, I named each category directory as WordPress would generate it (ex: "My Awesome Category" = "my-awesome-category")
Instead of a mod-rewrite, I dived into the code.
It's rather simple actually (pretty good for me considering I've just started with PHP in the past few weeks):
Open up: templates-functions-category.php
Around line 30, change:
$link = $file.$querystring_start.'cat'.$querystring_equal.$cat_ID;
$link = 'http://www.yoursite.com/categorydirectory/' . $category_nicename . '/';
That's all ;)