1) Notice them sooner and deal with it--either ask them to come back later, or be proactive and start talking, or ignore them. A monitor mirror makes it easy to notice when they're doing it.
2) You'd rather they interrupt you, they'd rather not interrupt you. Too late, but they think they're being polite.
I don't see how anything there is rude, but I probably have mild Asperger's. If you don't want it to happen again ask them to send a (whatever messaging system you use) note to get your attention.
Other options:
* Get an "On Air" or equivalent sign. Train your humans to respect it with the caveat that if you're expected to have office hours, people are going to bother you.
* Have office hours and train your humans to only bug you during those office hours.
* Get a focused sound beam that pierces their heads so it's too uncomfortable to stand behind you. Or randomly spin around in your chair and strike them down.