What is the smallest I can shrink my Linode's disk to?

First try to resize your disk to 1 MB. The resize operation will fail, but don't worry.

You can now get the minimum size your disk can be resized to if you go into the dashboard in the old Linode Manager and look at the error message for the resize operation which reports the smallest number of 4KiB blocks you can make your disk. Lets say the error reported in the Linode Manager says:

fs_resize: resize failed resize2fs 1.44.0 (7-Mar-2018) /vbin/bin/resize2fs: New size smaller than minimum (1289947)  

You will take the number of blocks (1289947) and multiply it by the size of each block (4KiB) and then divide by the number of KiB in a MiB (1024) to get the smallest size your disk can be. You will want to round this number up to the nearest MiB. (MBs in the Linode Manager are technically MiBs or multiples of 1024*1024 bytes)

Hint: For this example, I can type in Google's search bar: 1289947 * 4 KiB to MiB or 1289947 * 4 /1024 and get 5038.85547. I take the answer and round it up to 5039 which is the smallest size I can make my disk in MiB with the amount of data contained on it.

Note: Occasionally the smallest amount may be slightly wrong, so if it still fails to resize, you will want keep to adding a small amount to the answer you get and try again.

Warning: For large disks with lots of data, this operation can take a long time and cannot be stopped without corruption of data, so you may want to do the resize operation in a number of smaller stages gradually getting the disk down to the minimum size.

The way I did it, to avoid having to resize the disk, was to first fill unused space with zeroes using zerofree ( http://manpages.ubuntu.com/manpages/xenial/man8/zerofree.8.html ) and then pipe the image through a compression program like xz.

Example command line:
ssh root@178.79.163.69 "dd if=/dev/sda | xz" | dd of=linode4.img

Thanks go to the fine folks at the #linode IRC channel for helping me with this :)