Among other things, always make sure you have the latest video card drivers.
Be sure to download RF-Mod 3.5 and C-Mod 4, as they fix the speed on many low-end machines. Also download the Noob Edition mod to speed up the performance.
It is worth noting that, for some people, dual core or dual processors cause lag in the game. If you have one of these setups, go to the task manager (ctrl alt + delete, you might have to click the task manager box) and go to processes. Find the fretsonfire.exe and right click, choose Set Affinity and untick one of the processors listed. While you are here, you might as well right click and set the priority higher as well.
If you are runnning FretsOnFire on Vista, you may run into some lag as well on older versions of FoF. The easiest way to fix this problem is to set FoF's compatability mode to Windows 2000 using these steps.
1) Right click your fretsonfire.exe
2) Go to properties and go to compatability
3) Set "Compatibility Mode" to Windows 2000
Also, if you are experiencing extreme lag, make sure you are running the game using a color quality of 32bit (in the Display Properties Settings)
Noob Edition - thread with version for 1.1.324
Noob Edition - thread with version for 1.2.451