Well first you have to Zero Erase and format the drive GUID OS X Extended J (or another format if your going to work with PC's)
Reducing bad sectors effect on hard drives
Drives, partitions, formatting w/Mac's + PC's
Next i would start with movies as they are the largest culprit and take up a lot of room.
Get the drive below 50% filled if possible. Create new folders on the external drive and just move the contents, not the main folders.
Then I would get another blank powered external drive and Carbon Copy Cloner the OS X parition to the external, hold the option key to boot from it then use Disk Utility to Erase with Zero the internal OS X partition then revverse clone back.
This will defrag your entire OS X boot partition and place all the data up nice and close together, user files being last as they expand and contract into free space.
your OS X and apps will be fast as a result.
Most commonly used backup methods explained