Seeing that you've just entered the light and decided to try out Mac OS X, I'd suggest getting an Intel Mac Mini. You'll be able to use the latest Mac OS X for the next few releases, and run Windows and windows applications at full speed.
To dual boot the machine with XP or Vista you would use Apple's built-in boot camp. You could also run Windows (and any Intel Platform OS) in a window within Mac OS X by using Parallels (at http://www.parallels.com).
Windows applications can also run directly on Mac OS X using WINE. There is a version for Intel Mac OS X here.
http://sourceforge.net/projects/darwine/
You could probably find an Intel Mac Mini Core Solo for around $300. This is a best buy if you know how to upgrade a CPU. The core solo CPU can be switched with a Core2Duo Merom chip. Plenty of stories here:
http://www.google.com/search?q=mac+mini+merom+upgrade
Of course, you can also upgrade a core duo, but what for? It costs a bit more in the second hand market (~$400) and will probably be fast enough already.
It may cost more than buying an older G3, but when you factor in the upgrades you'll want to install and the cost of Mac OS X 10.4, you might find that option cheaper. Also, with an Intel Mac you're buying both a Mac and a PC, so that's a real bargain.
Apologies to the group, I'm aware this is a PPC section, but I think it's better to suggest an Intel Mac to a new switcher from Windows since it allows them the option of using the computer with both Mac OS X and Windows at full speed.