AFAIK Bitcoin Core keeps an index (or something like that) of all of the transactions for the addresses so it may not look through the entire blockchain. However, getbalance and listunspent must still iterate through that list for each of the 16000 addresses in order to find which ones are still unspent and what the total balance is.
So what I'm saying is, with a mysql database, even of size 1,000,000 records you can SUM the balances of 16,000 records in fractions of a second.
I don't see why bitcoind cannot achieve the same performance?
I mean literally if I imported the data from bitcoind into mysql (a list of all my addresses and transactions), it would take me millionseconds to do these same queries?
At this point, I am not entirely sure. But, I believe that it has something to do with verifying each transaction e.g. checking the signature and scripts, however, as I said, I am not sure. I recommend that you take a look at the code and see if you can find the issue yourself. You can find the source at
https://www.github.com/bitcoin/bitcoin and there are developer docs, which are easier to follow, at
https://dev.visucore.com/bitcoin/doxygen/. The specific methods you are looking for are located in src/wallet/rpcwallet.cpp. If you do find that there is an issue with performance with no reasonable explanation, please open an issue with the developers, and perhaps write a patch and submit that to the core devs.