I tore apart a late 50's packard V8 with my students just for the Heck of it. Besides the fact it weighed a ton, it looked an awful lot like the engine in my 59 Cad.
I'm willing to bet that you can fit just about any GM engine w/o much modification.
I'm putting a Chevy 350 in a 41 caddy, and I 'm getting the same advice about big blocks, 472/500 Cads, etc. I chose chevy because 1) I already had the engine and 2) parts are plentiful and cheap.
As far as mpg goes, those old beasts weigh a lot. I would suggest an overdrive trans with fuel injected engine to get the best mileage.