I don't know enough about the sorts of requests that might be made against your database, but

1. if using MySQL 4+, have you turned on the query caching? and

2. can you pre-populate or generate any reports off-line? i.e. if you know the reports that most users ask for, can you pre-build them at 1-6 a.m. (or whatever), when it does not matter if each query takes three minutes.

Even running the queries will build the query cache for number 1.

Finding the top 20% of the reports used 80% of the time means you can pre-build those or prime the cache.

It all depends on your data and how dynamic the queries are.