"What's in a name? That which we call a rose
By any other name would smell as sweet." (Juliet)
So what's in a game? The subject has been discussed by folks far more eloquent and persuasive than I; but hey, this is Slashdot so what the hell. In some ways trying to define what 'game' means is akin to defining art; grasping at the wind. I think you're pretty close to the mark with your latter definition, although as sibling posters suggest the win condition is not necessary, and the concept of winning itself has been toyed with as a mechanism (see UnwinnableByDesign). "Fun" is hardly a necessity either, witness RPG grinds, for example. And how 'fun' would Contra be without UUDDLRLRBA?
That leaves "simulated environment", which I think approaches the heart fo the matter. Games (not just video games here) are a simulacrum, an approximation of a scenario. Some are more complex than others - Snakes and Ladders versus Dwarf Fortress or MilSim-du-jour - but all distill a scenario/environment into a set of rules. Fun and winning are usually part of the arrangement, but not by necessity.
Sibling post hit the mark too in saying that a significant proportion of gaming is there as a vehicle for storytelling. It's easy to be cynical as there are some bad stories out there. But there is good storytelling too, if that's your thing. Planescape: Torment* has a particular focus on story; and there are times where the line between 'game' and 'interactive story' are pretty heavily blurred. Dear Esther is an example which PA Report recommends quite highly:
Dear Esther is a $10 PC [note: currently on sale on Steam for £1.74 for the next two hours at time of writing] experience that toys with the concepts that make, or don’t make, a game. You are a man exploring a deserted island, and every so often you’ll trigger a voice over that helps to explain what you’re doing there and describes other characters you never see. It’s a desolate, lonely game that funnels you into one specific ending that’s impossible to escape. It takes around 90 minutes to finish, depending on how much of the island you choose to explore.
At the end of a day if someone creates something that is a representation of something with at least some semblance of interaction, and calls it a game I'm quite happy to believe them until proven otherwise.
*Planescape was recently discussed on /. and it was mentioned that GOG had it for ten bucks, which was nifty. Now they've discounted it to five bucks, which is at least twice as nifty by my calculations.