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

Another method is by buying a Steam code for that specific game and the guy giving you the code so you redeem and it's over.

Just as the other answers state, you do need to be a Steam friend to gift games to one another.

But, as an additional caveat, if you live in different regions, Steam will price your games differently. The price difference of the desired gift between your regions must also be minimal, (~less than 10%). Even if the price in the buyer's region is higher, Steam will not allow the inter-regional gifting due to price differences. There is no way around this.

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}