Thanks bladeforce! Wine 1.3.35 with PlayOnLinux worked a treat!
I set Wine to Win98 mode. I also set it to simulate a virtual desktop and to capture the mouse.
I installed from CD (note, don't let it install DX8), then downloaded the 1.0.96 patch, copied it into the POL Wineprefix drive for AVP and ran it, then downloaded the nocd hack and copied it into the installation directory for AVP2.
After that, ran the game and everything was great!
The only real wrinkle was that, during the install, it had to switch from disk 1 to disk 2. Obviously, you have to mount the CD before it can be seen by anything, but with Fedora's Automount process under KDE, you don't actually mount the CD until you browse it with Dolphin (or you do something manual, like 'mount /dev/cdrom /media'. However, if the drive was automounted to start with, simply ejecting the CD from the drive's 'eject' button doesn't always clear the old mount point. Ejecting the disk from the desktop or within Dolphin cleans everything up.
I had forgotten how bloody SCARY this game is. LOL