You will first run into a tallboy at the very beginning of Mission 5: Lady Boyle’s Last Party. They are heavily armored soldiers on stilts that shoot incendiary crossbow bolts from very long range. The easiest way to kill one with your sword is to use Bend Time 2 and Blink—it can be done with level 1 but you need to be at a slight height advantage. When you use Bend Time 2 every attack during the duration is considered an assassination, so even blinking from the front will automatically kill it.
If you do not have Bend Time 2 you can also blink from behind while unseen, or use a Drop Assassination to kill it as well.
If the Tallboy receives damage from an outside source, such as a grenade or pistol shot from another guard, the trophy can glitch out and not reward you for the kill. Be sure that the target has taken no damage prior to you assassinating it.
To see a complete walkthrough of a Tallboy being killed with a sword, please view the video below: