What I’d suggest is building a document with everything you hope to have included, with priorities associated with them. If the full set of features won’t fit, have in mind what gets cut and in which order. With any Arduboy game, it’s not a matter of if you hit the PROGMEM cap, it’s when.
By the time I was implementing the battle engine we had about 1500 bytes left. The shop and inn were also not implemented yet. I found more space, but everything was taken by the graphics (which could be limited to 1 or 2 tileset per over world sketch), music, text, menus, and whatever else. With a bigger emphasis on battling and capturing monsters I think a more complicated battle is definitely possible. This was just an explanation of my anxiety lol.