How can I optimize a table with lot of data?

I have a table with 728,000 entries.  Each entry has about 24 fields - six of which are formula fields.  

As you can well imagine, whenever I query this table, things tend to slow down, so I'm looking for ways to optimize it.  

Some questions: do formula fields perform more slowly than data fields (I've found this to be the case in Excel)? If so, would it make sence to convert the formulas to data fields?

Any other help regarding optimizing large data sets would be appreciated.