predcon: I really don't remember a whole lot of Windows 3.x games that weren't really DOS games. Wasn't SimAnt or It Came From the Desert or some other giant ant game on Win 3.x? It was a lot better on the Amiga. And a lot worse on the SNES. The same can be said of Lemmings. You're probably better off getting the licensed Amiga emulation package from Cloanto and snagging the Amiga analogues of the Windows 3.x games that you're wanting to play.
I think typically they came with a DOS version, or at least a bunch of them did. At that point Windows was mostly just a front end for DOS. I'm sure there were some APIs and such, but even up until about Win2k, DOS was always in the background to various extents.
Miaghstir: How well would VirtualBox and ReactOS run old Windows games? At least that is a free idea for someone to mess with. Yeah, ReactOS tries to imitate Windows NT rather than the DOS-based Windows 9x series, but it may work well enough anyway.
ReactOS is related to Wine, I'm unclear as to the extent, but there are some developers in common to the two, and IIRC they do use some of Wine's work for implementing portions of the OS.
Personally, on the rare occasion that I've run them, I haven't had much trouble with stability.
For those specifically interested in DOS games, one can also run FreeDOS as well. For that extra measure of nostalgia. Unfortunatelly, I think that they solved the scrapping for kilobytes of RAM bit of the experience.
There is always this, it's not complete and probably abandoned by now, but here's openwindows.
http://www.jankie.net/soedesh/20.htm