Always start by asking what users need to do with the data
Do they need to go into a specific record to look up info or make edits or bulk edits?
Put in easy search & filtering. Determine what are the general context users start with when it comes to finding data. Do they do a specific search (e.g. name, email, phone #) or by ranges? (e.g. by city, area codes, gender, age). Make sure your basic search functionality allows the user to readily perform searches of interest. If specific ranges are common search parameters, provide these as facets in a faceted search.
Question to ask: Are the users more likely to try to drill down to find their specific record or are they more likely to spiral out to find related records? "AND" Filters tend to work better for the former case and "OR" facets for the latter.
Or Do they need to survey their dataset and then perform actions on selected few?
In this case, it makes more sense to show them aggregated summary on their data in form of a dashboard. Then allow them the ability to drill down into specific records. This is more typical for admin and manager type users who needs to oversee things. The dashboard will have pre-defined target metrics put in place and can warn the user when something/somebody is under-performing.
If this is your use case, you need to speak more with your users to determine what are the metrics that matters and design the dashboard based on them. You'll also pair this with a simple record search for the times they do need to look at the details of a specific item.
Now onto the fun decisions
Pagination vs lazy loading
Are pages of results meaningful for the user? If this is a result set that the user will reference in the future, then yes pagination is helpful. If the current search result set is only relevant right now. (e.g. twitter feed list) then lazy loading makes more sense.
Example from JIRA search
Having a natural query language is a good idea for advanced/power users... especially if you need bulk edit functionalities. Keep in mind that regular users typically get intimidated by seeing an empty query box. Syntax aren't hard to learn, but it does need to be learnt. So always provide a simple search option with the advanced query option.
Also the dev efforts to put in natural query language isn't small... so unless your user base need to perform routine complex searches, you may not need this.
Save Searches / Sensible Defaults
Are users consistently conducting similar type of searches in the system? You might want to have a default set of search results load when the user first arrive on the page. If this is more of a general usage type of system, a default search set might make the most sense... e.g. list of most recently added entries. Sometimes searches may be user specific... in that case, it might be helpful if the system recalls their last search parameters and display that to them. If this is a more advanced internal tool, the ability to save search queries may be useful.