The levers, in order of how much they actually matter
Dimensions come first. File size scales with pixel count, so going from 640 px wide to 480 px removes about 44% of the pixels before a single encoder setting is touched. Frame count is next and scales almost linearly: halving the frame rate roughly halves the file.
Colour count is third and less linear than people expect — 256 to 128 colours often costs almost nothing visually while saving 20–30%, but 32 to 16 usually looks obviously worse for a much smaller gain. Dithering is last, and it can increase size: it trades flat compressible areas for noise that compresses worse, in exchange for smoother gradients.