Well first off I wouldn't recommend trying to power your client's database with the standard WordPress database instance. They can use WordPress for the website all they like. But with millions of records like that, you really don't want to move those data in with WordPress.

For that matter, you're probably gonna want a dedicated database server to answer those questions, if the client doesn't already have one. You might also need to investigate something like Elastic Search, depending on what your search requirements are and what sort of database they are using (pay close attention to whether or not it provides full text search ability).

Beyond that, and somewhat obviously, you're also gonna want SSL on the website and to make sure you're up to date on federal and state privacy requirements for data like this, as well as best practices for securely transferring data over the web (port configuration, ssh keys, etc).

The privacy concerns would raise a flag for me. If those data have anything personally identifiable in them - which they very probably do - then you're really gonna want to make sure you do your research on security of personally identifiable information. Government specific privacy /security /auditability requirements may also apply, so double check that too.