How can I estimate the time & size of each image file for different compression level of the Partimage program before the image is generated?
i.e. What is the time & size of image file required for no, gzip, bzip2 & lzo compression?
I want to use this information to decide which compression to create an image file of less than 600MB for a 60GB hard disk which has about 40GB data (67% full).

Time wise, it depends mostly on the speed of your hard drives assuming you have a relatively modern processor to do the compression; avoid writing the image to the same hard drive where the partition you are imaging resides.
Compression wise, you will not get a 60 or 70 to one compression rate with any of the above or anything else I can think of. It's not realistic to expect to image 40Gb of data down to a 600MB image. It depends on what kind of files you have, but with gz I get about 2 to 1 compression at about 400MB/min; bz gives a little better compression, maybe 2.5 to 1 but is much slower; I'm not familiar with lzo. YMMV.