If a non-friend comes across my Steam Wishlist, how easily can they gift me one of the games?

When purchasing a game for someone, you can only gift it to someone who is on your friends list. However, should you have a game in your Steam inventory - pretty rare nowadays - you can send that gift to anyone at all, just by knowing their email address. Once they accept the gift, you and that person will be added to each other's friends lists.

That someone needs to be a friend:

When you purchase a game on Steam, we offer the option to “gift” the item to anyone on your Steam friends list.

So it follows:

If you'd like to send it to someone who's not listed, you'll have to add them to your Steam friends list.

That seems to be the only prerequisite.

^{Source: Steam page on gifts}