Arduino Mega 2560 ADC sampling instant and other timings
does that mean that this is the instant from which the actual ADC
  conversion start, and so 1.5 ADC clock cycles from here, my analog pin
  value is set on hold?


Yes. After between 3μs and 5μs. This is because conversion start at the following rising edge of the ADC clock cycle. This rising edge might have just happened, which means you need to wait 31 (main) clock cycles.


  how can I know how much time passed before that sbi function call is
  issued?


You could copy the original code and create your own analogRead2 function that measures the time before setting ADSC.


  I saw that a single instruction on arduino won't take more than 4
  microseconds (but micros() function has that resolution so I don't
  exactly know!)


A single instruction will take 1 or 2 clock cycles (if I remember correctly). So at 16Mhz that will mean 62.5ns (nano seconds) per clock cycle. Not 4ms


  Now, considering the so called "first" conversion, which take 25 ADC
  clock cycles
  
  does this conversion happen just the first time I call analogRead
  since I powered on Arduino? or does it happen even after some time ,
  because the ADC module gets powered off? (of course, I consider the
  case when Arduino remains powered on all the time)
  
  Judging by the timings I measured it seems like that the former is the
  one really happening, even if I don't use ADC for some time, but can
  anyone confirm?


This first conversion is after the ADEN bit changes from 0 to 1. If you don't unset this bit, all further conversions will take the shorter time.

PS on the first conversion, the sample-and-hold takes place after the extra 12 ADC clock cycles, so between cycle 12 and 13.5.

PPS this info is actually based on the ATMega328, but should be pretty similar in the 2560.