@kaufman: Thanks for the feedback. I had an irrational fear that I have been doing something wrong in my testing and that the first user would totally fail to connect.
You may have noted that I added the search for on-device as a top-level category. Having it there makes sense to me because it is really part of the meta-metadata and isn't a lot different than a Read boolean column. You can long-press on "No" to restrict what is shown in all the other categories to books not on the device.