Wine is a pretty rough app, although it will run some Windows programs very well. I have been using VMware for a few years now and I really like it but it is fairly expensive, and it does require you to have a copy of Windows. VMware allows you to create a "virtual computer" containing "virtual hardware". You will do a full installation of Windows into this "Virtual PC" so you can basically run most any Windows app natively without any problem and without having to reboot.
In fact you can be running Linux as your base (host OS) and run many virutal machines under it. You might have a Windows 2000 virtual machine, a Windows 98 virtual machine etc, all running at the same time and you can switch between them with ease. Now I would not suggest VMware if the reason you want it is to run high end Windows games. But if you want it for running productivity types of apps (MS Office, IE, Outlook, Visio, etc, etc, etc) then it's *perfect*.
One other thing, you are going to need a pretty healthy machine for VMware to run well (two operating systems running at the same time might need twice the power and resources). I can tell you that I have an Athalon 1600+ with 512MB of RAM, and a GeForce2 w/32MB and it runs *great*. I can have Linux up, open Win98, BSD, and a couple of Solaris x86 machines all at the same time and my machine doesn't break a sweat.