Hashes actually never have to be computed on the device. They can be computed by Calibre and stored with the metadata. It doesn't even have to be hashes, a number that is incremented for each update of a book or metadata would do, as long as each book and set of metadata can be matched between devices. But as you say, it may not provide much benefit, if any at all.
The background connect I've mentioned before could be extended to also be used to keep the databases in sync, using low priority threads, but perhaps only when the device is charging and Calibre is active and option for background sync is activated.
To defuse anger about "poor performance" you could split CC into separate apps, that cooperate and share data.
1. Basic connection and "send to device from Calibre", along with an eBook browser and launcher. Like current version. (But with background receive mode added.
)
2. Addon to connect online to content server on Calibre and download books. The first of your options above.
3. Addon to allow remote offline Calibre browsing using a local copy of Calibre database and "queue fetch to device from Calibre". The second option above.
Charge for the first, and give the two others away for free, with a warning that they are only intended for users with adequate hardware and may not work as intended otherwise. That way you can perhaps minimize the anger from frustrated users?
Most likely it will be quicker to implement the online access, if I understand you correctly. Offline access may wait, until you see if there is a demand and you think it will increase sales. I doubt it, unfortunately, I suspect most users would be happy with online access or the basic functionality.