I would go 2ga with a 200 amp or so fuse, and carry a spare fuse in the car. Starter motors are rather power-hungry indeed, and if that main fuse blows none of your electrics will work.
Alot of people don't fuse the cable to their engine bay, reason being the starter motor draws that much current.
If you want cheap cable, go to a welding supplier and get some of the cable they use for welding leads.