Matewis: Have you tried getting close to the guard from behind before Alt+Right clicking? Also, you have to have the pistol and silencer as your active weapon.
Onlooker: Yes, I even tried getting so close to him that I was practically breathing down his neck. Still nothing. I also tried going as far back as possible while still being behind him, but no dice.
I think I had the pistol and silencer equipped. I bought it at the relay station and followed the instructions. I didn't see an equip menu anywhere, so I'm assuming it was equipped when I bought it? When I equipped the weapon, I did see a pistol and a silencer icon.
Just above the agent's portrait on the bottom left there is a weapon icon. If you click on that you can select which weapon to wield. The icon needs to be red, which will correspond with you seeing the pistol in your agent's hand.
Also, the game might distinguish between left alt and right alt, so make sure you try both. It's possible that there are alternative keys for assassinate as well. I think I read somewhere that you can Shift+right click as well, though I haven't tried it myself.
The assassinate thing is tricky for some reason. I never could do it in the tutorial either for some reason. I only figured it out later. I think my problem was that I either didn't have a weapon drawn, or I did but it wasn't the pistol.