At worst it's a few pages, but not entire books, let alone some exponentially huge thing you'd never encounter in reality.

That's only if your logical system is simple. If you're a human, then the system you're using is probably not a real logical system, and is anyway going to be rather large.

I think the halting problem is related, but I don't see how it's exactly equivalent.

See http://www.solipsistslog.com/halting-consequences-godel/