Am I correct in the assumption that the EEPROM read data are instantly available in the EEDR register after EERE bit is set?
Instantly is a bit exaggerated (see below), but let's say immediately, yes. At least, from the programmer's point of view, it is available right after, and the sample code clearly shows so.
Does this mean that a EEPROM read is about same fast a storing the data in SRAM?
How many cycles does a reap operation take?
From chapter 5.3.1 of the datasheet you linked:
When the EEPROM is read, the CPU is halted for four clock cycles before the next instruction is executed
And from chapter 5.2.1:
The internal data SRAM access is performed in two clkCPU cycles
Note that for SRAM, read and write timings are usually the same. So they don't really explicitly say it, but these two clock cycles should apply for both.
So a EEPROM read is slower than SRAM access (EEPROM needs you to set EEAR, EECR, and then there is a four cycle penalty, whereas for SRAM, there is only a two cycle penalty), but it is in the same order of magnitude.