Is this a linear-time operation where you have to find all transactions that deposited money into that account before you can know the 'balance'?
Yes. Fortunately, only the owner of the address ever needs to do this.
What can of performance hit could we expect once there are 1000's of transactions per block instead of just a half dozen or so?
It's not that hard to scan through transactions, especially if you're not actually verifying the crypto for each one (which a lightweight client doesn't need to do).