Wow, Mr. One Wheel Drive... I wish my management took that approach! I guess charging for parking to stop encouraging wasteful car use would be most simple, but that's of course a very negative thing to do to employee morale. I'd suggest offering to reimburse on request up to at least the cost of parking ($1200 annually) towards transit, bike expenses, or active wear, especially if your office is small enough that it's obvious who's commuting how. That would be a really nice thing to do to equally value your non-driving employees.
At my workplace, we're spread over two buildings, rented from different owners. One building charges for parking, but at my building, it's free, because the owner doesn't want to deal with the hassle (!) of a parking program. I'm in government, and rumour has it that Public Works actively tried to get paid parking at my location... bad optics to have free parking for government workers. It's the source of a fair amount of griping, since people are paid the same at both sites, and one gets free parking (but also is in a poor location and misses out on many other advantages that the other building has).
Personally, I'm just rolling my eyes because we have a couple of picnic tables up against a wall near our rear entrance, and the space between them gets hand-shoveled all winter (I guess it's considered to be part of the entrance). Bike racks in the parking lot? Snowed right in. Nobody* bikes in winter, but apparently we might do outdoor lunch! :D
The facility managers at my site actually have a very negative approach to cycling. It has definitely influenced me to consider working elsewhere, and I'm now looking forward to a 9 month temporary job in a different branch of government that will have me commuting along the river paths to a bike-friendly office all summer, starting in two weeks. So, commuter appreciation matters!
*actually, about 1% of the employees at the site bike in winter, about 10% in summer.