Do remember that if you add too many indexes to spead up reads, writes can get very slow. I had a table with a supporting index and removing that index caused writes do from 2-3 seconds to near instant. Clustering correctly also means a lot. And do defragment the database (very important on rotating disks). Try to get a look at which indexes can be removed (if possible). The database could maintain information enough to give clues about this. Some databases also can suggest indexes to make.
Could also be a locking issue (table locks where row locks are enough).
At any rate, getting a clear overview over where the time is used is the first task. Hitting randomly and hoping will take too long.