A couple of scripts provided by cloud-utils call qemu-img so cloud-utils should require qemu-utils. However, qemu-utils pulls in a lot of dependencies which are all unnecessary (and undesired) for cloud images. I suggest to break the package into separate subpackages like Ubuntu does. A metapackage cloud-utils, a subpackage for cloud images which contains growpart and ec2metadata and another subpackage for all the rest.
Also, there are some very Ubuntu-specific scripts that I think need to be removed.
I can help with this work if I can be made a co-maintainer.