Check the indexes.
The bigger the database, the more overhead is used during queries. So if your code is something like:
http://example.com/page.php?page_id=21
.. then you'd want to make sure whatever 'page_id' uses from your database is an index.
As well as any other large tables. (Most commonly, 'id' is the primary call, so make sure 'id' is an index)
Additionally, do you optimize the database regularly? If no, you need to optimize periodically to clear out the clutter. (If you use phpmyadmin, there's an easy "select all" option with a pull-down for optimize right beside it).
Do a ping/tracert and see what your response time is like, if it's greater than 70-80ms consistently, contact your host and give them a copy of the ping/tracert.
If all that fails, then consider building a cache for your most intensive queries.