There are lots of other things that have to be asked. Like how many fields? Are you using unstored calculations? Are you having to do many searches via relationships?
My biggest table had about 20 fields, all stored, combination of numbers, text and date. It had about 83 million records. Finds really only took about 3-5 seconds over the LAN.
But I've brought a database to its knees with only about 1000 records with complicated unstored calcs and complicated relationships.