You can already differentiate contacts by category.

Each contact has classes:
person
personid-{the contact id}
catid-[the category id]

You can use those classes and CSS to modify the look of your contacts depending on the categories they belong to.

For instance, use

.person.catid-10 { font-size: 10px }

to change the font size of contacts being members of the category that has id 10.

It's not possible to add a category id to personlist since personlist can be a group of contacts from different categories. That would only work if contacts were of the same category. In which case, why the need to differentiate by category?

If you are using modules, each module instance has its own id, that is how you can differentiate several module instances on a page. If contacts are of the same category in each module instance, it's easy to differentiate them from each other.

To change the look of contacts with different categories in a single module instance or in a menu item, catid_[id] is the only way to go.