From my conversations with Dropbox support I understood that Dropbox really can't handle a large number of small files. The large plans are intended for people who store large files, not lots of stuff.
The indexation doesn't need to happen immediately upon boot. Do one directory every minute or so, let the computer start up and do other things while your background task runs.
Changes are detected because the operating system notifies dropbox of changes made, they're not continuously scanning the drive. From other comments it sounds like dropbox has registered a hook like that for the entire filesystem, instead of just the working folder. That seems unnecessary.
Why can't Dropbox remember the state of the files in your dropbox folder, and upon login, grab state of the files on the Dropbox server and do a simple comparison, without re-calculating hashes for the files on your computer?
I guess the methods I propose will not guarantee proper syncing if for some reason a file has changed but the metadata hasn't...
I haven't used Dropbox in a while as a local client for other reasons but I think people need to appreciate this is the payoff for having the convenience? How can one expect it to sync changes if it never scans or detects changes? People seem to want a magical product where it never uses any HD throughput or CPU to index/scan/upload megabytes of data, sure it can look for changes less often but that decreases the usefulness of the product.
As a sidenote, surely all the dropboxers use dropbox for everything (they have unlimited accounts) so they must be 100% aware of this? in which case there must be concrete reasons for this!?