Best way to use Linux to assign local LAN IP to a WAN machine running Windows securely so that programs which need to communicate on the local network may do so.

The server side can be complicated, although I would prefer it not to be. However, the client side (windows) must be a simple install wizard else the person who wants to use it will never figure it out.

I believe this falls under VPN, which OpenVPN (http://openvpn.net/) seems to be the most referenced FOSS implementation. Is this what people here would recommend?

OpenVPN will work. L2TP is perhaps slightly easier to set up on the client side, as the required functionality already exist in Windows (nothing needs to be installed), but you will need certificates at both ends unless you use the same pre-shared key for all clients (I believe the same is true for OpenVPN).

SSTP is another alternative, and one that is both supported by Windows clients and will pass through just about any firewall. I haven't tried setting up a Linux SSTP server (of which there seems to be exactly one implementation), so I can't vouch for its stability or usability.

Whatever you choose to do, just stay away from PPTP. It has major security issues.