Currently using bitcoind 0.11 headless on Debian (although had the same issue with all previously bitcoind versions).

The wallet info:
Wallet.dat size: 160MB
Number of addresses: ~16,000
Unspent outputs: (varies but around: 20-40)

Load on the server seems fairly low, and CPU usage is very low.
Memory: 4GB
load average: 0.39, 0.43, 0.35
Drive is SSD

"listunspent" function is extremely slow; and by extension this seems to affect getbalance and sendmany/sendtoaddress functions.

Here are some specific examples of this sluggishness:

$ time /path/to/my/bitcoin/bitcoin-cli getbalance "" 3
real    0m3.398s
user    0m0.008s
sys     0m0.004s

$ time /path/to/my/bitcoin/bitcoin-cli listunspent
real    0m4.213s
user    0m0.008s
sys     0m0.004s

The times are consistently 3-4 seconds every time

But then some commands are much quicker:

$ time /path/to/my/bitcoin/bitcoin-cli getinfo
real    0m0.039s
user    0m0.004s
sys     0m0.004s