New atmega238p works way too *slow*

How did you flash that AtMega? Out of the box ( as it comes from ATMEL/MicroChip ) the processor runs with its internal oszilator and the clockspeed is 1MHz. You have to set the fuses correctly to use an external 16MHz quartz.