Can defiantly see your issue, and I also agree with what GotDibbs response with not showing anything to the user when the page first loads is a bad idea. I would suggest getting some end user feedback on what they commonly look for to build the initial data table contents. While having the ability to slowly bring data in as the user request it is great, but it would be much better if the user can just land on the page and find what they need 90% of the time is even better. (Not sure if this is possible based on how the data you currently have is being used by your users).
To help cut down on your initial load problem I would like to add another possible (implementation) solution with the use of the DataTable jQuery Plugin. The plugin has a lot of the filtering features built right in and also has a way to Ajax in some of your data to help cut down on initial page load. Depending on how you want to setup the plugin; data can be pulled in as user use the pagination feature or change filtering options/values.
This plugin is defiantly a top pick with our end user as it provides a super intuitive interface. The response time seems to be instantaneous when filter/search for contents already in the table. Development teams also like it as the API is well written and easy to customize the implementation needed. I will have to admit we have never thrown the plugin a data table with over 1000+ records on load through. We have done around 300 hundred and the plugin took it like a champ.