Muss der Bootloader dann auch 1024 Worte lang sein oder was hat es damit auf sich?
Der Bootloader muß nicht, er darf max. 1024Worte lang sein. Entscheidend ist die sich daraus ergebende Startadresse. Die Fusebits Einstellungen müssen mit dem erzeugten Hex-File übereinstimmen, sonst startet der Boootloader nicht. Über die BOOTSIZ Fusebits wird ja durch die Länge des Bootloaders gleichzeitig die Startadresse des Bootloaders festgelegt.
Wenn dein Bootloader fertig ist und kleiner als 512 Worte ist, kannst du das ja immer noch ändern.

Kann ich eigentlich den ATmega168 auch mit einem 20 MHz Quarz betreiben, wenn ich den vorhandenen durch solch einen ersetze?
Warum nicht, probier es halt aus. Bei 20Mhz läuft der mega168 allerdings nur ab 4,5V.