Hello.
One thing maybe worth noting is that Cyclone III has inbuilt DDR and DDR2 interface. Maybe the Altera software has free core for it?
EP3C40 with even more logic is also available in PQFP240 package, but is expensive at about 65 euros.
EDIT: If BGA style package are used, you could fit it underside a 68060 socket to gain small PCB area. Also QFP144 will fit, but it will have little I/O. (Spartan-3E400, EP3C5,10,16,25)