Hmm... I have found in the past that you can make some good strides by looking at not only the SQL statement, but how its used in the context of the system.

The real question is, where are you spending your time? Is it in the SQL query itself, in the record fetching, in the comparison? If you're making a lot of small queries, perhaps there is a way to combine them into a few larger queries.

It sounds like you're fetching a fair amount of rows (60k+). Is there a way you can reduce the number of rows you're grabbing, perhaps by caching the data on the client side, so you don't have to grab all the data every time? Or allow the user to filter the data better, so they don't have to look at as much data?

Without knowing some of the business requirements and more about the environment, its hard to make pointed suggestions, but hopefully it can give you something to think about.