There really isn't a canonical answer to this since it would depend on disk subsystem speeds, fragmentation, etc. so it doesn't quite fit this format well.
That said, if it's a "clone" of the drive, it will try to copy the entire drive, sector by sector. The way to get the end image smaller is to compress it.
Backups are generally done at the file level. Clones/images are drive level. You probably need to use either cloning with compression or a true backup program that will copy files and compress the files, not the resulting filesystem image file.
Another thing to check since you mentioned partimage is what filesystem you have on the USB drive. Even if it's a 16 gig drive, if the filesystem can't handle a single 4 gig file, the clone may fail and some open source programs do not handle failure gracefully...you might have been sitting for four hours with a program that's not even running anymore or is "stuck".