I think that at the beginning of a turn a little icon should appear (like the ones that scroll down on the side), if a rebel army appears in your territory.
It can give information like, what terrirory, and perhaps it can have different titles such as "Large brigand army has appeared in XXXX Settlement" for a large rebel army, and something like "Minor brigand army has appeared in XXXX Settlement" for a smaller rebel army.

What do you guys think?
I think it will be helpful, because as your empire gets larger, sometimes I overlook a small rebel army when I am scrolling across the map; (especially when the city boxes are in the way).

Also quick question: Do rebels take away from the local city's population?