The basic part of the Adafruit_PCD8544 library which your 'almost empty code' initialises takes up a fair bit of space, 20% on an Arduino UNO for instance, not much you can do about that.
I can't use a 1602 because all (box, front case, pcb) is already designed :S BUT.... I take off the atmega8 and put an atmega328p. Now it's works fine ready to program.