how much space does a given package, and dependencies, cost?

Simplest and bug free way to get the space used by a program and all its dependencies is to use apt itself. Note dependencies that are not used by another program, but installed with a package, is not considered as they are not removed.
Simply

sudo apt-get --assume-no autoremove PACKAGENAME

or

apt-space-used-by() { sudo apt-get --assume-no autoremove $@ | grep freed | cut -d' ' -f4-5 ;}

usage apt-space-used-by PACKAGENAME

This python script looks promising (bigpkg - find packages that require a lot of space on your system)

• Simply try following command ( to get disk space freed by purge):

  echo -n | sudo apt-get purge <package> | grep "disk space will be freed"
  

  or

  echo -n | sudo apt-get purge --auto-remove <package> | grep "disk space will be freed"
  

  where replace <package> with your package-name ( example: gimp)

  This will not purge package with dependencies but only gives how much disk space will be freed with help of grep!

• Using dpkg --print-avail or apt-cache show:

  apt-cache show <package> | grep "Installed-Size"
  

  or

  dpkg --print-avail <package> | grep "Installed-Size"
  

  This will display installed size of <package>.

  Example:

  $ apt-cache show gimp | grep "Installed-Size"
  Installed-Size: 15024
  

• Sort list of installed packages by size

  dpkg-query -W -f='${Installed-Size;8}  ${Package}\n' | sort -n
  

  You can use more for page-wise:

  dpkg-query -W -f='${Installed-Size;8}  ${Package}\n' | sort -n | more
  

  Above list packages according to size acceding, you can use tail to list packages consuming top size as follows:

  dpkg-query -W -f='${Installed-Size;8}  ${Package}\n' | sort -n | tail
  

• Using dpigs (from man dpigs):

  dpigs - Show which installed packages occupy the most space

   dpigs sorts the installed packages by size and outputs the largest ones. Per default dpigs displays the largest 10 packages. You can change
     this value by using the -n option (see "OPTIONS"). The information is taken from the dpkg status file with grep-status(1) 

  This Can be installed by: sudo apt-get install debian-goodies
  Example of run command

  $ dpigs
  115449 wine1.6-i386
  110356 linux-image-extra-3.13.0-24-generic
  103828 libreoffice-core
  86240 fonts-horai-umefont
  74016 libreoffice-common
  72709 liboxideqtcore0
  61736 linux-headers-3.13.0-24
  60821 libpyzy-1.0-0
  59477 firefox
  59443 thunderbird
  

• Finding size of Unused package:-

  popularity-contest (8) - list the most popular Debian packages
  popcon-largest-unused (8) - List size of unused packages
  

  First run popularity-contest and then popcon-largest-unused, This will help you to find size of unused package. Visit man-pages for more information.

I tried my best to provide useful commands by steps.
Hope these helps!

apt-cache show packagename lists, among other things, the installed size of a package and the dependencies of a package. There's also apt-cache rdepends packagename to list the packages that use that package.

You might want to use the latter command and apt-cache policy packagename to determine if a reverse-depdendency is installed.

Here is a script which does that. No machine-friendly output though.

sudo apt-get install python-apt

and you're ready to go.

#!/usr/bin/env python2
# -*- coding: utf-8 -*-

from __future__ import (absolute_import, division,
                        print_function, unicode_literals)
import apt
from apt.cache import Filter, FilteredCache

MB = 1024*1024

class InstalledFilter(Filter):
    def apply(self, pkg):
        return pkg.is_installed

def iter_base_deps(cache, package):
    deps = []
    version = package.installed
    for dep_type in ('Depends', 'PreDepends', 'Recommends'):
        deps.extend(version.get_dependencies(dep_type))
    for dep in deps:
        for base_dep in dep:
            if base_dep.name in cache:
                yield base_dep

def main():
    package_ref_count = {}
    results = []

    cache = FilteredCache(apt.Cache())
    cache.set_filter(InstalledFilter())
    for package in cache:
        for base_dep in iter_base_deps(cache, package):
            if base_dep.name in package_ref_count:
                package_ref_count[base_dep.name] += 1
            else:
                package_ref_count[base_dep.name] = 1

    for package in cache:
        base_deps_size = 0
        base_deps = []
        for base_dep in iter_base_deps(cache, package):
            if package_ref_count[base_dep.name] == 1:
                base_deps.append(base_dep)
                base_deps_size += cache[base_dep.name].installed.installed_size
        total_size = package.installed.installed_size + base_deps_size
        results.append((total_size, package, base_deps_size, base_deps))

    for total_size, package, base_deps_size, base_deps in sorted(results, reverse=True):
        if package.name in package_ref_count:
            continue
        if total_size < MB:
            break
        self_size = package.installed.installed_size
        base_dep_count = len(base_deps)
        print('{:.1f} MB  {}'.format(total_size/MB, package.name) + \
              (' with {} deps'.format(base_dep_count) if base_dep_count else ''))
        if base_dep_count:
            print('    {:.1f} MB  self'.format(self_size/MB))
            for base_dep in base_deps:
                size = cache[base_dep.name].installed.installed_size
                print('    {:.1f} MB  {}'.format(size/MB, base_dep.name))


if __name__ == '__main__':
    main()

Example output:

72.6 MB  gthumb with 4 deps
    3.0 MB  self
    61.0 MB  libwebkit2gtk-3.0-25
    8.0 MB  gthumb-data
    0.1 MB  gstreamer0.10-gnomevfs
    0.5 MB  flex