Indexing strategy for dynamic predicate
If I were you I would run a trace specific to hits on that table.  It shouldn't be overly intensive since you are restricting it to just queries against that table, from your application.  Run just the minimum needed by the DTA (Database Tuning Advisor).  Run it for a day here, a day there, make sure you get some end of week days and some end of month days.  Then run the whole lot through the DTA.

Here is why, I'm willing to bet that you have specific combinations of columns that are going to come up more often than not.  You can create more complex indexes based on that information.  You might also find that you can create some correlated statistics. Basically statistics that have more than one column.  For example creating a statistic on City and State together may improve queries against those two columns.

However make sure you don't create to many indexes.  On a table that large I'm guessing you do a fair number of writes and every additional index added will slow them down.  Of course you may do most of your writes during a batch process.

Also make sure that you put an automatic process to update your statistics periodically.  With that many rows the statistics aren't going to update on their own very often.  Only once 500+20% of the rows have changed, in at 500 mil rows that's a LOT.