Best practice for time machine backups over a network.

Don't forget the basics, such as verifying the network's actual throughput. For example, if you are using Gigabit Ethernet confirm it's actually realizing that speed in Network Preferences. Wireless throughput should be similar, at least for recent equipment, but it can go up and down depending on an ever-changing wireless environment.

Then, test the ability to back up and restore entire folders containing large numbers of sacrificial files (for example).

Then, regardless of your observations, implement redundancy in your backup strategy. In my opinion simplicity and redundancy are more important than speed.

Everyone's needs are different. Beware of advice from omniscient Internet experts — who don't even use Time Machine — yet gleefully dispense all sorts of misinformation about it. They appear even on this site (not so much recently though).

In the past we used Time Capsule, which was fine at the time, but with files getting bigger and those devices getting old we need to move on.

You can just as easily connect that same drive to a Time Capsule or AEBS's USB port.

A TC's internal hard disk drive is replaceable (with some difficulty).

Assuming I can get all that to function successfully, what surprises am I likely to encounter if I ever need to restore the iMac from that backup?

Try it and find out for yourself. Let no one attempt to convince you otherwise.

Does it have to be done over the network?

No.

If we are looking for a faster solution, can the SSD be connected directly to the iMac to be restored?

Sure, but you must bear in mind the "overhead" of Time Machine renders the vastly superior speed of a SSD utterly irrelevant. This applies to backing up as well as restoring.

You're better off purchasing several, redundant, inexpensive, traditional, slow, rotating hard disk drives. When they fail (not if but when), just throw it out. Unlike SSDs, hard disks almost always give you some warning of impending failure, and can even be used for a long time after exhibiting signs of failure.

Frequent "Time Machine has to create a new backup" warnings are such a sign. A typical hard disk drive will last for years even after encountering that warning. When they become intolerably frequent just trash the drive. As long as it is encrypted it's completely useless to anyone else.

It's a good idea to keep your backup drives geographically separate from one another at all times. I think you have that covered but it's worth repeating. One and only one backup is obviously insufficient. Two backups are better, but the two are certain to be near each other for at least short periods of time making them equally subject to simultaneous loss / damage / theft. The implication is the need for a minimum of three backup devices to approach 100% assurance of disaster recovery.

Or would the fastest usable connection be to hardwire both machines to the network hub and restore ?

It's still a network connection, and as such is not likely to be much different than a wireless network connection. The exception is if your wireless environment is hopelessly crowded, in which case you're probably already using a wired network.