Time Machine not backing up

The same thing is happening.. You have recovered space inside the sparse bundle.. but there is insufficient space left on the disk .. TM needs lots of room to sort files into the sparsebundle.

If you managed to delete a large number of files out of the sparsebundle what you need to do now is compact the sparse bundle.

The details here are a bit older but still should work.

https://blog.fosketts.net/2015/07/22/how-to-use-mac-os-x-sparse-bundle-disk-images/

look at the section on compact or compressing the sparsebundle (compress is not the right term.. you are simply removing the free space).

IMHO this is a very temporary fix.. and with High Sierra.. the Time Machine backup to a network drive is already flakey.

I would wipe the drive and start afresh with new clean backup.

If you want to keep the old backups.. use the option to archive the TC to a USB drive.. equal size to TC or larger. Mac formatted.

Once that is completed I would do a one pass erase. (Zero Out Data in Apple Speak) It is going to double check every track on the disk to maintain integrity. It will take near to a full day to do it.. so make sure you start it at a suitable time.. the router will still work but obviously no backups can take place while it is low level formatting the disk.

But a quick erase is usually fine if the TC is not that old.

Screenshots are not displaying properly this morning.. sigh!! If you cannot see them I will repost.

The Time Capsule is fine handling multiple Macs .. Each Mac stores it's backup in a sparse bundle. This is a virtual disk.. so works like a partition. It will never conflate the backups. However the disk will run out of space faster. It is surprising how much space is used over time. And Time Machine needs plenty of free space.. so running multiple computers I would never plan on using more than 80% of the disk.

FYI, both i-Macs are running Mojave, and I should point out that my new i-Mac would of necessity be a full backup of the entire computer, i.e., applications and documents, which would require at least 500 GB, whereas my wife's computer is older and has many Time Machine backups, so additional backups require little drive space.

Your profile is showing High Sierra.. Mojave will make no difference in terms of reliability. They both have issues with network drives.

I do think erasing the TC and starting over is worth it. As mentioned if you want to preserve backup then do use archive function .. otherwise just erase and start afresh. I would start the backup on your wife's computer first.. once completed do yours.. ethernet is strongly recommended when you run first backup.. if that is possible. The backup can take half the time or less if wireless signal is poor.. and making a solid first backup helps.

Using a Synology is a great replacement for the TC .. but it does not need two disk.. the backup will still use sparse bundles.

As a btw.. since you have two iMacs.. you could also do the backup directly.. from one Mac to the other.. using a large USB drive. Since High Sierra Apple has supported Time Machine extensions from the server install being used on the standard distribution.. in some ways this is better as it uses SMB protocol. TC is old and will forever be stuck on AFP.

See this article on setting up network backups.

https://www.howtogeek.com/330288/how-to-set-up-your-mac-to-act-as-a-networked-time-machine-drive/

Let me also add.. this might also be useful to making a bootable clone with Carbon Copy Cloner. This has generally proven to be a lot more reliable than Time Machine.. but there is no reason you cannot run both. Large USB disks are readily available and you can partition them into suitable sizes for both CCC and TM on both computers.

You can also then have the TC working as a spare backup, tucked away to provide some redundancy.

Can I use one of the <> ports on the back of my TC to connect via an Ethernet cable to one (or both?) computer at a time and back them up via Time Machine

Yes, but be sure to turn off the WiFi on the Mac(s) to make sure that the backup will be over the wired Ethernet connection.

and then go back to Wi-Fi for the smaller backups?

Yes

Would that work and be faster and more reliable than using Wi-Fi for the initial large backups?

Yes, backups over Ethernet will always be 2-3 times or more faster than WiFi and more reliable as well, since there is much less to go wrong over a wired connection compared to wireless

Ps. I am using Mojave (10.14.3), so have no idea why you are seeing High Sierra.

Your profile shows your using 10.13

You probably forgot about setting it. Look at the bottom of your first post..