You might find that the design tools for foxpro (assuming you're talking visual FP) are better than the gui's I've used for MySQL.
What are you storing that it's not relational? I guess you're talking a single table rather than a database.
You might still find that the views available in fox (again assuming vfp) can help speed your queries. That's alot of records.
Say you're storing news items and the user wants the last weeks. I'd then query the view called news7days. You would probably get better performance through a view than through a straight query on a table. Easy to prove using seconds().
I'll be following this posting as I'm interested to see other opinions.