Have you ever heard of caching? In theory, if the binary code hasn't changed, then if the NaCl module is cached properly, you'd only have to download it the first time. Of course, you'd have to redownload it anytime it changes on the server, but look at it this way - you get instant access to updates.
And if you read the article, Google's purpose in this is not to create huge, full applications in native code and then run them through the browser, but combine this native calculations with the cloud. In Photoshop, that might mean your computer's GPU handles all the image processing, but all the data to save and export to different formats is sent to the cloud for processing. Or, Google Docs' spreadsheets could offload all the cell formula calculations in native code, rather than sending a request back to the server. The point of this native code is to speed up lots of little actions, not build entire applications.