Electronic – Do eeprom page writes always cost the same time as byte writes

It's not just write cycles that's specified, but erase/write cycles. On the AVR EEPROM can be erased by byte. Erasing sets all bits to 1, writing selectively clears bits. You can't program a 1, just 0s. If you want to set at least one bit to 1 you have to erase that byte.
Erasing removes the charges from the FET's floating gate, but on each erase cycle some of the charge remains on the floating gate, which won't be removed through the quantum tunneling. This charges accumulates and after a number of cycles there's so much charge left on the floating gate that the bit still will read 0 after erasure. That's what determines EEPROM life, it's erasure rather than writing. So you can safely write additional 0s, as long as you don't erase.
As a result, if the datasheet specifies 100k erase/write cycles you can have maximum 800k write cycles, one bit at a time, for 100k erasures.

If you're using only part of the EEPROM memory space you can extend its life by distributing the data, like Matt says this is called wear leveling.
The simplest method of wear leveling when writing blocks of data is to include a counter with the data. Suppose you need to keep 14 bytes of data. Add a 17-bit counter as two bytes, you probably have a bit to spare for the 17th bit. Increment the counter before writing the block of 16 bytes. If the counter has reached 100 000 you know this block is becoming unreliable, so you move to the next 16 bytes. Use this until it is worn as well. And so on. A 4k memory consists of 256 sixteen byte blocks, so you can extend the original 100k cycles to 25 million.
It should be obvious that your gain is greater with smaller blocks of data.

further reading
data retention on a microcontroller

The page size is 16 bytes, as stated in the datasheet.

The Page Write mode allows up to 16 bytes to be written in a single Write cycle, provided that they are all located in the same page in the memory: that is, the most significant memory address bits are the same. If more bytes are sent than will fit up to the end of the page, a condition known as ‘roll-over’ occurs. This should be avoided, as data starts to become overwritten in an implementation dependent way.

Page 14.

So your 1KBit memory has 8 pages, each 16 bytes in size.