Is 3 bytes a min to address a register in a 256K EEPROM?
No, your reasoning is not correct.

Firstly, let's look at your maths.

The device is 256kbits.  That means that it contains an array of 32kbytes, which equals 32768 bytes.

32768 is 215, so an address can be represented using 15 bits, or rounded up, just 2 bytes.

That is, you have addresses 00000000 00000000 to 01111111 11111111.

You can tell all that by looking at figure 5-2 in the datasheet you linked to:



So after sending the control byte you then send 2 address bytes.  Any data bytes follow that sequence.  So yes, that is three bytes in total, but only two of them are the address.

Setting that address only needs to be done once per write sequence.  You aren't limited to just writing one byte.

Once you have set the address you can write up to 64 bytes (or up to the end of the current 64-byte page) without having to send a new address.  So you could set the address to 23 and then write bytes 23, 24, 25, 26, 27.  That would be a total of 3 bytes for the control + address, then 5 bytes for the data totalling 8 bytes.  If you calculate 8/5, you get 1.6, which could be said to be the transaction "efficiency". For every byte of EEPROM you write like that you need 1.6 bytes to do it.  Writing more bytes at a time improves that efficiency.

The best efficiency is to write an entire page at once, which would be \$\frac{3+64}{64}=1.046875\$.

When it comes to reading things are slightly different.  This is because the chip maintains its own internal address pointer for reading.  Once you have set the address it automatically increments to the next address after reading.

Setting the address takes 3 bytes as before - the control byte plus the two address bytes.  But then to actually read you need to perform another transaction with another control byte.  So to read one byte takes 1+2+1+1 bytes.  That would be an efficiency of \$\frac{1+2+1+1}{1}=5\$ which is not that efficient at all.  Things get much more efficient though if you make use of that internal address pointer and read multiple bytes.  To take the example addresses we used for  writing, the efficiency for reading would be \$\frac{1+2+1+5}{5}=1.8\$ - a huge increase in efficiency.

So there are other small tricks you can use.  If you want to read two bytes that are close to each other in EEPROM it can actually be more efficient to do a sequential read of the entire memory between the two bytes of interest and throw away the bytes you're not interested in.

And yes, this is pretty much typical of all EEPROM devices in this class. But then they're not really intended to be particularly fast - they are intended to contain small amounts of configuration information for a system which is read once during startup and not referenced that much from then on.  For faster, heavier throughput you would normally use a serial Flash device instead of EEPROM. They are greater capacity and more efficient to access, but writing to them is more convoluted since you have to erase an entire page before writing it.  They are often used these days as the BIOS chips in computers - especially laptops - where there's a lot of reading and not much writing.