Improve query speed for large, wide table
For your example query:
         SELECT * FROM claims
         WHERE gender='F'
         AND age BETWEEN 16 AND 20
         LIMIT 100000;
try to add index on age.
But I suggest to use "SQL SERVER PROFILER" and "Database Engine Tuning Adviser" to monitor your queries, and then add suitable indexes, and make suitable changes.