Got Lands of Lore 2 to work under Fedora Core 1 using Cedega. Here is the script I used to run the game:

cedega -use-pthreads n -winver win95 ~/TransGaming_Drive/WESTWOOD/LOLG/lolg95.exe

I had to turn of 3d acceleration to get rid of black rectangles which surrounded some bitmaps. Game kind of locked up at the very end after I "killed" Belial so I couldn't see the ending.