When you get one of the tougher monsters as your first monster, you literally cannot win against it before you have a pile of two or three beating on you. I suggest the first level or two should only spawn normal (5ish hp it seems?) monsters and not the tankier ones that prevent you from doing anything.
Meta progression would also feel pretty good even if it was small boosts to stats. Also maybe some guaranteed stats per level like hp, and maybe .1/.2 attack.