>1) Set it up in cron to run between midnight and 3am.
This one won't work since you want it running all the time.
>2) Nice the process to 19.
This one lowers the priority and if another process is running on your server it will get more CPU resources. The admin folks have to set this up for you. This may work but it will cause the fatsearch to take longer to generate for spiders and surfers.
>3) Debug the script to increase performace.
Are you using any of your own databases? If so, that could be the bottleneck since searching those is probably using more CPU resources than accessing remote engines. You could try disabling any databases and do some fatsearches and have the admin people check the resources.