Glowing red eyes, a buff on your character that says "evil is afoot", or even just a message that indicates the player that is approaching you has criminal acts on.
Currently players can open up combat and hit you for 150+ damage with a single arrow. Hermits and nubs like myself would at least stand a bit more of a chance given some warning.
This sort of change would also encourage friendly player interaction since you have at least some assurance that the other player isn't going to attack you on sight (or is and you need to run).
Thematically it makes sense to indicate a person is going to shred you to pieces (weapons readied ect).
To make this viable/useful a related change might have to be made to "timing" where a player can't turn Criminal Acts on and immediately attack someone (Consider a 5 second grace period after the indication has been fired to surrounding players). "Player X is looking for trouble."